Novinky zeměměřické knihovny č. 3/2006

Klíčová slova: algoritmus, vektorová generalizace, simplifikace

Shrnutí

 Bylo odvozeno mnoho metod pro zjednodušování průběhu čar, ale jejich vyhodnocení zůstává otevřenou otázkou. Předložená práce se pokouší o hodnocení různých algoritmů pro automatické zjednodušování čar, co do jejich polohové přesnosti a doby potřebné k vlastnímu provedení.  Dřívější výzkumné práce týkající se takových vyhodnocování se obvykle soustřeďovaly na měření rozdílů v poloze čáry, která se měla zjednodušit, a jejím zjednodušeným tvarem. Ale původní čára obsahuje polohovou neurčitost. Tento příspěvek vyhodnocuje provádění algoritmů pro zjednodušování čar při využití dvou vyčerpávajících měřítek polohové přesnosti zjednodušené čáry. Tato dvě měřítka zahrnují jedno měřítko posunu a jedno měřítko zkreslení tvaru. Obě dvě jsou schopna vzít v úvahu jak posuny vznikající rozdíly původní a zjednodušené čáry, tak i polohovou neurčitost původní čáry.

Dosavadní stav: Vektorová generalizace je nenahraditelná při tvorbě papírových map z digitálních, zahrnuje v sobě kvalitu mapy ve zmenšeném měřítku, analyzuje data v mapě obsažená různým stupněm podrobností, redukuje ukládání dat a vytváří mapu pomocí jiných map při odlišném stupni podrobností.

Přitom generalizace čar představuje těžiště vektorové generalizace. Jedním z přístupů takové generalizace je zjednodušování čar, což je automatizovaný postup v GIS pro odstraňování nadbytečných dat v souboru digitálních dat. Zjednodušování čar zavádí polohovou chybu výsledné mapy a může vytvářet topologické chyby. Polohová chyba vzniklá algoritmem pro zjednodušování čar  se běžně porovnává s polohovou chybou Douglas-Peuckerova algoritmu, který interaktivně vyhledává kritické body na základě celého průběhu čáry. Tento algoritmus zahajuje počátečním odhadem pomocí zjednodušené lomené čáry - spojnice prvního a posledního vrcholového bodu lomené čáry. Pak se zbývající vrcholy ověřují co do blízkosti. Překračují-li vrcholy zadanou toleranci  ε > 0, pak se vloží co nejodlehlejší  vrchol zjed-nodušené lomené čáry. Rekurzí vše pokračuje až se dosáhne zjednodušení v rámci tolerance. Douglas-Peuckerův algoritmus se uká-zal jako nejúčinnější při zachovávání tvaru čáry.

Topologické chyby, které mohou vznikat při zjednodušování čar, mohou být: vzájemné křížení čar, souběžnost čar nebo nulová délka zjednodušené čáry. (Lee ve svém příspěvku Geographic and cartographic contexts in generalization = Zeměpisné a kartografické souvislosti při generalizaci), v Proc. of ICA Workshop on Generalization and Multiple Reprezentation, Leicester 2004) navrhl způsob vyhledávání topologických chyb.

Algoritmy pro zjednodušení čar

Článek pak probírá v dalším vyhodnocení těchto algoritmů pro zjednodušení čar: postupy s n body, postupy využívající vzájemné vzdálenosti mezi body a postupy s kolmou odlehlostí bodů, Reumann-Witkamovu rutinu, zhlazovanou lomenou čáru (http://www.proz.com/kudoz/48274), Opheimův, Langův  Douglas-Peuckerův a Visvalingam-Whyattův zjednodušovací algoritmus.

Vyhodnocení nejistoty při zjednodušování čar

Autoři pak u uvedených metod postupně testují měření největší odlehlosti, ověření datového souboru oceněním algoritmu pro zjednodušování čar a hodnocení algoritmů pro zjednodušování čar. Svou práci předkládají i na příkladu z části pobřežní čáry ostrova Hong Kong obsahující 1 500 bodů z digitální geografické báze dat B1000 Územního infromačního střediska (Land Information Centre, Surveying and Mapping Office, Lands Department, Hong Kong Special Administrative Region).

Závěrečné poznámky

Automatická generalizace se vyvinula během čtyř desetiletí a vznikly různé automatické algoritmy. Polohová přesnost zjednodušené čáry se měřila odlehlostí a tvarovým zkreslením.

Ukazuje se, že Douglas-Peuckerův algoritmus je nejpřesnější generalizací, ale vyžaduje příliš času. Proto pro mnohé praktické užití v GIS lze doporučit Langův nebo Zhao-Saalfeldův algoritmus. Oba poskytují vyšší přesnost než zbývající algoritmy.

Pozn. překladatele: Podrobnější řešení této otázky nastiňuje Clodoveu Davis ve své práci Výpočetní geometrie pro geografické informační systémy (Geometria Computacional para Sistemas de Informaçao Geográfica), na kterou lze také běžně nahlížet na internetové adrese www.dpi.inpe.br/gilberto/livro/geocomp/geometria.pdf a která je součástí nyní čtyřdílného souboru Zpracování geografických informací : teorie a aplikace (Geoprocessamento : Teoria e Aplicações), projektované řady vydávané Gilbertem Cãmarou, Antõnio Miguelem Monteirem a Clodoveu Davisem.