Back

ⓘ Ramer-Daglas-Peker Algoritam




                                     

ⓘ Ramer-Daglas-Peker Algoritam

Ramer–Daglas–Peker algoritam je algoritam za smanjivanje tačaka u krivoj koja je odredena pomoću serije tačaka. Originalan oblik algoritma je bio samostalno predložen 1972 godine od strane Urs Ramera, a potom dodatno doraden 1973 od strane Davida Daglasa i Tomasa Pekera i još nekoliko ljudi tokom naredne decenije. Ovaj algoritam je takode poznat pod imenima Daglas–Peker algoritam, interaktivni end-point fit algoritam i podeli-i-spoji algoritam.

                                     

1. Ideja

Svrha algoritma je da datoj krivoj sačinjenoj od linijskih segmenata nade sličnu krivu sa manjim brojem tačaka. Algoritam definise razlike na osnovu najvećeg rastojanja izmedu originalne i uprošćene krive Hausdorfova distanca izmedju krivi. Uprošćena kriva se sastoji od podgrupe tačaka od originalne krive.

                                     

2. Algoritam

Početna kriva je uredena 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 izmedu 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 nade 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 izmedu 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 takode 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.

                                     

2.1. Algoritam 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. MATLAB kod za toliko ne-parametarski RDP algoritam je dostupan ovde.

                                     

3. Aplikacija

Algoritam se koristi za obradu vektorske grafike i uprošćavanje u kartografiji.

Algoritam se široko koristi u robotici 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.

                                     

4. Kompleksnost

Kompleksnost ovog algoritma se može opisati pomoću linearne rekurzije T n = 2 T n/2 + O n, koja ima rešenje pomocu Master teoreme T n ∈ Θn log n. Medutim, najgora moguća kompleksnost je Θ n 2.

                                     

5. Reference

  • 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
  • Urs Ramer, "An iterative procedure for the polygonal approximation of plane curves", Computer Graphics and Image Processing, 13, 244–256 1972 doi:10.1016/S0146-664X7280017-0
  • R.O. Duda and P.E. Hart, "Pattern classification and scene analysis", 1973, Wiley, New York
  • 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
  • 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 102, 112–122 1973 doi:10.3138/FM57-6770-U75U-7727
                                     

6. Spoljašnje veze

  • JTS, Java Tolopogy Suite, sadrzi mnoge java implementacije, ukljucujuci javadoc for Douglas-Peucker algorithm
  • Implementation of Ramer–Douglas–Peucker and many other simplification algorithms with open source licence in C++
  • Implementation in F#
  • 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
  • XSLT implementation of the algorithm for use with KML data.
  • Ruby gem implementation