Рамер-Даглас-Пекер Алгоритам

Рамер–Даглас–Пекер алгоритам (РДП) је алгоритам за смањивање тачака у кривој која је одређена помоћу серије тачака. Оригиналан облик алгоритма је био самостално предложен 1972 године од стране Урс Рамера, а потом додатно дорађен 1973 од стране Давида Дагласа и Томаса Пекера^[1] и још неколико људи током наредне деценије.^[2] Овај алгоритам је такође познат под именима Даглас–Пекер алгоритам, интерактивни енд-поинт фит алгоритам и подели-и-споји алгоритам.

Идеја[уреди | уреди извор]

Сврха алгоритма је да датој кривој сачињеној од линијских сегмената нађе сличну криву са мањим бројем тачака. Алгоритам дефинисе 'разлике' на основу највећег растојања између оригиналне и упрошћене криве (Хаусдорфова дистанца измедју криви). Упрошћена крива се састоји од подгрупе тачака од оригиналне криве.

Алгоритам[уреди | уреди извор]

Почетна крива је уређена група тачака или линија и растојања димензије ε > 0.

Алгоритам рекурзивно дели линију. . У почетку су већ дате све тачке које се налазе између почетне и крајње тачке криве. Почетна и крајња тачка су аутоматски означене да треба да буду сачуване. Алгоритам онда нађе тачку која је најудаљенија од линијског сегмента који је означен претходно сачуваном почетном и крајњом тачком. Ова тачка је очигледно најдаља на криви од линијског сегмента између крајњих тачака. Ако је та тачка на мањем растојању од ε до линијског сегмента, онда се могу се занемарити све тачке које нису означене да требају бити сачуване; при чему поједностављена крива неће бити погоршана у односу на ε.

Ако је растојање тачке која је најдаља од сегмента веће од εонда та тачка мора да буде сачувана. Алгоритам сам себе позива рекурзивно са почетном тачком и најдаљом тачком а потом са најдаљом тачком и крајњом тачком, при чему такође маркира најдаљу тачку да треба бити сачувана.

Када је рекурзија извршена, нова крива може да буде генерисана састојећи се од свих тачака које су биле обележене за чување.

Непараметарски Рамер-Даглас-Пекер[уреди | уреди извор]

Корисник је углавном тај који дефинише ε.Као и код већине корекција линија базираним на методи проналажења кључних тачака, он може бити учињен непараметарски користећи границу грешке при дигитализацији као услов за елиминисање.^[3] МАТЛАБ код за толико не-параметарски РДП алгоритам^[4] је доступан овде.^[5]

Псеудокод[уреди | уреди извор]

(Под претпоставком да је унос низ)

function DouglasPeucker(PointList[], epsilon)
    // Naci tacku sa najvecom distancom
    dmax = 0
    index = 0
    end = length(PointList)
    for i = 2 to ( end - 1) {
        d = perpendicularDistance(PointList[i], Line(PointList[1], PointList[end])) 
        if ( d > dmax ) {
            index = i
            dmax = d
        }
    }
    // Ako je tacka veca od epsilon rekurzivno uprosti
    if ( dmax > epsilon ) {
        // Recursive call
        recResults1[] = DouglasPeucker(PointList[1...index], epsilon)
        recResults2[] = DouglasPeucker(PointList[index...end], epsilon)
 
        // konstruisati izlaznu krivu
        ResultList[] = {recResults1[1...length(recResults1)-1], recResults2[1...length(recResults2)]}
    } else {
        ResultList[] = {PointList[1], PointList[end]}
    }
    // vratiti rezultat
    return ResultList[]
end

Апликација[уреди | уреди извор]

Алгоритам се користи за обраду векторске графике и упрошћавање у картографији.

Алгоритам се широко користи у роботици^[6] за упрошћавање и уклањање сметњи у информацијама стечених помоћу ротирајућег даљиномера; у овој области више је познат као подели-и-споји алгоритам.

Комплексност[уреди | уреди извор]

Комплексност овог алгоритма се може описати помоћу линеарне рекурзије $Т (н) = 2 Т (н/2) + О (н)$ , која има решење (помоцу Мастер теореме) $Т (н) \in Θ(н лог н)$ . Међутим, најгора могућа комплексност је $Θ (н 2)$ .

Референце[уреди | уреди извор]

Урс Рамер, "Ан итеративе процедуре фор тхе полyгонал аппроxиматион оф плане цурвес", Цомпутер Грапхицс анд Имаге Процессинг, 1(3), 244–256 (1972) . дои:10.1016/С0146-664X(72)80017-0. Недостаје или је празан параметар |титле= (помоћ)
Давид Доуглас & Тхомас Пеуцкер, "Алгоритхмс фор тхе редуцтион оф тхе нумбер оф поинтс реqуиред то репресент а дигитизед лине ор итс царицатуре", Тхе Цанадиан Цартограпхер 10(2), 112–122 (1973) . дои:10.3138/ФМ57-6770-У75У-7727. Недостаје или је празан параметар |титле= (помоћ)
Јохн Херсхбергер & Јацк Сноеyинк, "Спеединг Уп тхе Доуглас–Пеуцкер Лине-Симплифицатион Алгоритхм", Проц 5тх Сyмп он Дата Хандлинг, 134–143 (1992). УБЦ Тецх Репорт ТР-92-07 аваилабле ат https://web.archive.org/web/20160414023022/http://www.cs.ubc.ca/cgi-bin/tr/1992/TR-92-07
Р.О. Дуда анд П.Е. Харт, "Паттерн цлассифицатион анд сцене аналyсис", (1973), Wилеy, Неw Yорк (https://web.archive.org/web/20110715184521/http://rii.ricoh.com/~stork/DHS.html)
Висвалингам, M., анд Wхyатт, Ј.D. "Лине Генералисатион бy Репеатед Елиминатион оф тхе Смаллест Ареа". (1992) ЦИСРГ Дисцуссион Папер Сериес Но 10, Университy оф Хулл, 16 пп (https://web.archive.org/web/20140210052537/http://www2.dcs.hull.ac.uk/CISRG/publications/DPs/DP10/DP10.html)

Референце[уреди | уреди извор]

^ Сее тхе Референцес фор море детаилс
^ Хецкберт, Паул С.; Гарланд, Мицхаел (1997). „Сурвеy оф полyгонал симплифицатион алгоритхмс” (ПДФ): 4.
^ Прасад, Дилип К.; Леунг, Маyлор К.Х.; Qуек, Цхаи; Цхо, Сиу-Yеунг (2012). „А новел фрамеwорк фор макинг доминант поинт детецтион метходс нон-параметриц”. Имаге анд Висион Цомпутинг. 30 (11): 843—859. дои:10.1016/ј.имавис.2012.06.010.
^ Прасад, Дилип К.; Qуек, Цхаи; Леунг, Маyлор К.Х.; Цхо, Сиу-Yеунг (2011). А параметер индепендент лине фиттинг метход. 1ст ИАПР Асиан Цонференце он Паттерн Рецогнитион (АЦПР 2011), Беијинг, Цхина, 28-30 Нов. дои:10.1109/АЦПР.2011.6166585.
^ Прасад, Дилип К. „Матлаб соурце цоде фор нон-параметриц РДП”. Приступљено 15. 10. 2013.
^ Нгуyен, Виет; Гäцхтер, Стефан; Мартинелли, Агостино; Томатис, Ницола; Сиегwарт, Роланд (2007). „А цомпарисон оф лине еxтрацтион алгоритхмс усинг 2Д ранге дата фор индоор мобиле роботицс” (ПДФ). Аутономоус Роботс. 23 (2): 97. дои:10.1007/с10514-007-9034-y. Архивирано из оригинала (ПДФ) 17. 09. 2010. г. Приступљено 17. 05. 2016.

Спољашње везе[уреди | уреди извор]

[1] Сее тхе Референцес фор море детаилс

[2] Хецкберт, Паул С.; Гарланд, Мицхаел (1997). „Сурвеy оф полyгонал симплифицатион алгоритхмс” (ПДФ): 4.

[3] Прасад, Дилип К.; Леунг, Маyлор К.Х.; Qуек, Цхаи; Цхо, Сиу-Yеунг (2012). „А новел фрамеwорк фор макинг доминант поинт детецтион метходс нон-параметриц”. Имаге анд Висион Цомпутинг. 30 (11): 843—859. дои:10.1016/ј.имавис.2012.06.010.

[4] Прасад, Дилип К.; Qуек, Цхаи; Леунг, Маyлор К.Х.; Цхо, Сиу-Yеунг (2011). А параметер индепендент лине фиттинг метход. 1ст ИАПР Асиан Цонференце он Паттерн Рецогнитион (АЦПР 2011), Беијинг, Цхина, 28-30 Нов. дои:10.1109/АЦПР.2011.6166585.

[5] Прасад, Дилип К. „Матлаб соурце цоде фор нон-параметриц РДП”. Приступљено 15. 10. 2013.

[6] Нгуyен, Виет; Гäцхтер, Стефан; Мартинелли, Агостино; Томатис, Ницола; Сиегwарт, Роланд (2007). „А цомпарисон оф лине еxтрацтион алгоритхмс усинг 2Д ранге дата фор индоор мобиле роботицс” (ПДФ). Аутономоус Роботс. 23 (2): 97. дои:10.1007/с10514-007-9034-y. Архивирано из оригинала (ПДФ) 17. 09. 2010. г. Приступљено 17. 05. 2016.

[1]

[2]

[3]

[4]

[5]

[6]