Ramer-Daglas-Peker Algoritam
Ramer–Daglas–Peker algoritam (RDP) je algoritam za smanjivanje tačaka u krivoj koja je određena pomoću serije tačaka. Originalan oblik algoritma je bio samostalno predložen 1972 godine od strane Urs Ramera, a potom dodatno dorađen 1973 od strane Davida Daglasa i Tomasa Pekera[1] i još nekoliko ljudi tokom naredne decenije.[2] Ovaj algoritam je takođe poznat pod imenima Daglas–Peker algoritam, interaktivni end-point fit algoritam i podeli-i-spoji algoritam.
Ideja
Svrha algoritma je da datoj krivoj sačinjenoj od linijskih segmenata nađe sličnu krivu sa manjim brojem tačaka. Algoritam definise 'razlike' na osnovu najvećeg rastojanja između originalne i uprošćene krive (Hausdorfova distanca izmedju krivi). Uprošćena kriva se sastoji od podgrupe tačaka od originalne krive.
Algoritam
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/30/Douglas-Peucker_animated.gif/220px-Douglas-Peucker_animated.gif)
Početna kriva je uređena grupa tačaka ili linija i rastojanja dimenzije ε > 0.
Algoritam rekurzivno deli liniju. . U početku su već date sve tačke koje se nalaze između početne i krajnje tačke krive. Početna i krajnja tačka su automatski označene da treba da budu sačuvane. Algoritam onda nađe tačku koja je najudaljenija od linijskog segmenta koji je označen prethodno sačuvanom početnom i krajnjom tačkom. Ova tačka je očigledno najdalja na krivi od linijskog segmenta između krajnjih tačaka. Ako je ta tačka na manjem rastojanju od ε do linijskog segmenta, onda se mogu se zanemariti sve tačke koje nisu označene da trebaju biti sačuvane; pri čemu pojednostavljena kriva neće biti pogoršana u odnosu na ε.
Ako je rastojanje tačke koja je najdalja od segmenta veće od εonda ta tačka mora da bude sačuvana. Algoritam sam sebe poziva rekurzivno sa početnom tačkom i najdaljom tačkom a potom sa najdaljom tačkom i krajnjom tačkom, pri čemu takođe markira najdalju tačku da treba biti sačuvana.
Kada je rekurzija izvršena, nova kriva može da bude generisana sastojeći se od svih tačaka koje su bile obeležene za čuvanje.
Neparametarski Ramer-Daglas-Peker
Korisnik je uglavnom taj koji definiše ε.Kao i kod većine korekcija linija baziranim na metodi pronalaženja ključnih tačaka, on može biti učinjen neparametarski koristeći granicu greške pri digitalizaciji kao uslov za eliminisanje.[3] MATLAB kod za toliko ne-parametarski RDP algoritam[4] je dostupan ovde.[5]
Pseudokod
(Pod pretpostavkom da je unos niz)
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
Aplikacija
Algoritam se koristi za obradu vektorske grafike i uprošćavanje u kartografiji.
Algoritam se široko koristi u robotici[6] za uprošćavanje i uklanjanje smetnji u informacijama stečenih pomoću rotirajućeg daljinomera; u ovoj oblasti više je poznat kao podeli-i-spoji algoritam.
Kompleksnost
Kompleksnost ovog algoritma se može opisati pomoću linearne rekurzije T(n) = 2T(n/2) + O(n), koja ima rešenje (pomocu Master teoreme) T(n) ∈ Θ(n log n). Međutim, najgora moguća kompleksnost je Θ(n2).
Reference
- Urs Ramer, "An iterative procedure for the polygonal approximation of plane curves", Computer Graphics and Image Processing, 1(3), 244–256 (1972) . doi:10.1016/S0146-664X(72)80017-0. Недостаје или је празан параметар
|title=
(помоћ) - David Douglas & Thomas Peucker, "Algorithms for the reduction of the number of points required to represent a digitized line or its caricature", The Canadian Cartographer 10(2), 112–122 (1973) . doi:10.3138/FM57-6770-U75U-7727. Недостаје или је празан параметар
|title=
(помоћ) - John Hershberger & Jack Snoeyink, "Speeding Up the Douglas–Peucker Line-Simplification Algorithm", Proc 5th Symp on Data Handling, 134–143 (1992). UBC Tech Report TR-92-07 available at https://web.archive.org/web/20160414023022/http://www.cs.ubc.ca/cgi-bin/tr/1992/TR-92-07
- R.O. Duda and P.E. Hart, "Pattern classification and scene analysis", (1973), Wiley, New York (https://web.archive.org/web/20110715184521/http://rii.ricoh.com/~stork/DHS.html)
- Visvalingam, M., and Whyatt, J.D. "Line Generalisation by Repeated Elimination of the Smallest Area". (1992) CISRG Discussion Paper Series No 10, University of Hull, 16 pp (https://web.archive.org/web/20140210052537/http://www2.dcs.hull.ac.uk/CISRG/publications/DPs/DP10/DP10.html)
Reference
- ^ See the References for more details
- ^ Heckbert, Paul S.; Garland, Michael (1997). „Survey of polygonal simplification algorithms” (PDF): 4.
- ^ Prasad, Dilip K.; Leung, Maylor K.H.; Quek, Chai; Cho, Siu-Yeung (2012). „A novel framework for making dominant point detection methods non-parametric”. Image and Vision Computing. 30 (11): 843—859. doi:10.1016/j.imavis.2012.06.010.
- ^ Prasad, Dilip K.; Quek, Chai; Leung, Maylor K.H.; Cho, Siu-Yeung (2011). A parameter independent line fitting method. 1st IAPR Asian Conference on Pattern Recognition (ACPR 2011), Beijing, China, 28-30 Nov. doi:10.1109/ACPR.2011.6166585.
- ^ Prasad, Dilip K. „Matlab source code for non-parametric RDP”. Приступљено 15. 10. 2013.
- ^ Nguyen, Viet; Gächter, Stefan; Martinelli, Agostino; Tomatis, Nicola; Siegwart, Roland (2007). „A comparison of line extraction algorithms using 2D range data for indoor mobile robotics” (PDF). Autonomous Robots. 23 (2): 97. doi:10.1007/s10514-007-9034-y. Архивирано из оригинала (PDF) 17. 09. 2010. г. Приступљено 17. 05. 2016.
Spoljašnje veze
- Implementation of Ramer–Douglas–Peucker and many other simplification algorithms with open source licence in C++
- XSLT implementation of the algorithm for use with KML data.
- You can see the algorithm applied to a GPS log from a bike ride at the bottom of this page
- Interactive visualization of the algorithm
- Implementation in F#
- Ruby gem implementation
- JTS, Java Tolopogy Suite, sadrzi mnoge java implementacije, ukljucujuci javadoc for Douglas-Peucker algorithm