Википедија

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 уреди

 
Pojednostavljenje dela linearne krive pomocu Daglas-Peker algoritma.

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 уреди

Reference уреди

  1. ^ See the References for more details
  2. ^ Heckbert, Paul S.; Garland, Michael (1997). „Survey of polygonal simplification algorithms” (PDF): 4. 
  3. ^ 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. 
  4. ^ 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. 
  5. ^ Prasad, Dilip K. „Matlab source code for non-parametric RDP”. Приступљено 15. 10. 2013. 
  6. ^ 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 уреди

Преузето из „https://sr.wikipedia.org/w/index.php?title=Ramer-Daglas-Peker_Algoritam&oldid=26781979”