Algoritmus Ramer – Douglas – Peucker - Ramer–Douglas–Peucker algorithm
The Algoritmus Ramer – Douglas – Peucker, také známý jako Douglas – Peuckerův algoritmus a iterativní algoritmus přizpůsobení koncového bodu, je algoritmus, který decimuje křivka složená z úseček na podobnou křivku s menším počtem bodů. Byl to jeden z prvních úspěšných algoritmů vyvinutých pro Kartografická generalizace.
Idea
Účelem algoritmu je, daný křivka složená z úseček (který se také nazývá a Polyline v některých kontextech), najít podobnou křivku s menším počtem bodů. Algoritmus definuje „nepodobný“ na základě maximální vzdálenosti mezi původní křivkou a zjednodušenou křivkou (tj. Hausdorffova vzdálenost mezi křivkami). Zjednodušená křivka se skládá z podmnožiny bodů, které definovaly původní křivku.
Algoritmus

Počáteční křivka je uspořádaná sada bodů nebo čar a kóta vzdálenosti ε > 0.
Algoritmus rekurzivně rozděluje čáru. Zpočátku jsou uvedeny všechny body mezi prvním a posledním bodem. Automaticky označí první a poslední bod, který se má zachovat. Poté najde bod, který je nejvzdálenější od úsečky s prvním a posledním bodem jako koncovými body; tento bod je zjevně nejvzdálenější na křivce od přibližné úsečky mezi koncovými body. Pokud je bod blíže než ε do úsečky, pak všechny body, které nejsou aktuálně označeny k uchování, mohou být zahozeny, aniž by zjednodušená křivka byla horší než ε.
Pokud je bod nejvzdálenější od úsečky větší než ε z aproximace pak musí být tento bod zachován. Algoritmus se rekurzivně nazývá prvním bodem a nejvzdálenějším bodem a poté nejvzdálenějším bodem a posledním bodem, který zahrnuje nejvzdálenější bod označený jako ponechaný.
Po dokončení rekurze lze vygenerovat novou výstupní křivku skládající se pouze ze všech bodů, které byly označeny jako uchované.

Neparametrický Ramer – Douglas – Peucker
Volba ε je obvykle definováno uživatelem. Stejně jako většina metod pro přizpůsobení linek / polygonální aproximace / dominantní bod lze provést neparametrické použití chyby vázané v důsledku digitalizace / kvantizace jako podmínky ukončení.[1]
Pseudo kód
(Předpokládá se, že vstup je jedno založené pole)
funkce DouglasPeucker (PointList [], epsilon) // Najděte bod s maximální vzdáleností dmax = 0 index = 0 end = délka (PointList) pro i = 2 až (end - 1) {d = perpendicularDistance (PointList [i], Line (PointList [1], PointList [end])) -li (d> dmax) {index = i dmax = d}} Seznam výsledků [] = prázdný; // Pokud je maximální vzdálenost větší než epsilon, rekurzivně zjednodušte -li (dmax> epsilon) {// Rekurzivní volání recResults1 [] = DouglasPeucker (PointList [1 ... index], epsilon) recResults2 [] = DouglasPeucker (PointList [index ... konec], epsilon) // Sestavení seznamu výsledků ResultList [] = {recResults1 [1 ... délka (recResults1) - 1], recResults2 [1 ... délka (recResults2)]}} jiný {ResultList [] = {PointList [1], PointList [end]}} // Vrátit výsledek vrátit se Seznam výsledků []konec
Odkaz: https://karthaus.nl/rdp/
aplikace
Algoritmus se používá pro zpracování vektorová grafika a kartografická generalizace. Ne vždy zachovává vlastnost non-self-křižovatky pro křivky, což vedlo k vývoji variantních algoritmů.[2]
Algoritmus je široce používán v robotice[3] provést zjednodušení a potlačení dat rozsahu získaných rotací rozsah skeneru; v tomto poli je známý jako algoritmus split-and-merge a je mu přiřazen Duda a Jelen.[4]
Složitost
Doba běhu tohoto algoritmu při spuštění na křivce skládající se z segmenty a vrcholy jsou dány opakováním kde je hodnota index v pseudokódu. V nejhorším případě nebo při každém rekurzivním vyvolání a tento algoritmus má provozní dobu . V nejlepším případě nebo při každém rekurzivním vyvolání, v takovém případě má provozní doba známé řešení (prostřednictvím hlavní věta o dělení a dobývání opakování ) z .
Použití (plně nebo částečně)Dynamický konvexní trup datových struktur lze zjednodušení prováděné algoritmem dosáhnout v čas [5].
Viz také
Alternativní algoritmy pro zjednodušení řádků zahrnují:
Další čtení
- Urs Ramer, „Iterativní postup pro polygonální aproximaci rovinných křivek“, Počítačová grafika a zpracování obrazu, 1 (3), 244–256 (1972) doi:10.1016 / S0146-664X (72) 80017-0
- David Douglas a Thomas Peucker, „Algoritmy pro snížení počtu bodů potřebných k reprezentaci digitalizované čáry nebo její karikatury“, The Canadian Cartographer 10 (2), 112–122 (1973) doi:10.3138 / FM57-6770-U75U-7727
- John Hershberger a Jack Snoeyink, „Urychlení algoritmu pro zjednodušení Douglas-Peuckerovy linie“, Proc, 5. sympatie k zpracování dat, 134–143 (1992). UBC Tech Report TR-92-07 k dispozici na http://www.cs.ubc.ca/cgi-bin/tr/1992/TR-92-07
- R.O. Duda a P.E. Hart, „Klasifikace vzorů a analýza scény“, (1973), Wiley, New York (https://web.archive.org/web/20110715184521/http://rii.ricoh.com/~stork/DHS.html )
- Visvalingam, M; Whyatt, JD (1992). Zobecnění vedení opakovanou eliminací nejmenší oblasti (Technická zpráva). Diskusní příspěvek. Výzkumná skupina pro kartografické informační systémy (CISRG), University of Hull. 10.
Reference
- ^ Prasad, Dilip K .; Leung, Maylor K.H .; Quek, Chai; Cho, Siu-Yeung (2012). "Nový rámec pro neparametrické metody detekce dominantních bodů". Výpočet obrazu a vidění. 30 (11): 843–859. doi:10.1016 / j.imavis.2012.06.010.
- ^ Wu, Shin-Ting; Marquez, Mercedes (2003). „Douglas-Peuckerův algoritmus, který se neprotíná,“. 16. brazilské sympozium o počítačové grafice a zpracování obrazu (SIBGRAPI 2003). Sao Carlos, Brazílie: IEEE. str. 60–66. CiteSeerX 10.1.1.73.5773. doi:10.1109 / SIBGRA.2003.1240992. ISBN 978-0-7695-2032-2.
- ^ Nguyen, Viet; Gächter, Stefan; Martinelli, Agostino; Tomatis, Nicola; Siegwart, Roland (2007). Srovnání algoritmů extrakce linek pomocí dat 2D rozsahu pro vnitřní mobilní robotiku (PDF). Autonomní roboti. 23 (2). 97–111. doi:10.1007 / s10514-007-9034-r.
- ^ Duda, Richard O.; Hart, Peter E. (1973). Klasifikace vzorů a analýza scény. New York: Wiley. ISBN 0-471-22361-1.
- ^ Hershberger, John; Snoeyink, Jack (1992). Urychlení algoritmu zjednodušení Douglas-Peuckerovy linie (PDF) (Technická zpráva).
externí odkazy
- Boost.Geometry podporuje Douglas – Peuckerův zjednodušující algoritmus
- Implementace Ramer – Douglas – Peucker a mnoha dalších zjednodušujících algoritmů s open source licencí v C ++
- Implementace algoritmu XSLT pro použití s daty KML.
- Algoritmus aplikovaný na protokol GPS z jízdy na kole ve spodní části této stránky
- Interaktivní vizualizace algoritmu
- Implementace ve F #
- Implementace drahokamu Ruby
- JTS, Java Topology Suite, obsahuje implementaci Java mnoha algoritmů, včetně Douglas-Peuckerův algoritmus