Filtrace VectGen Vhodnou modifikací Jenksova přístupu je algoritmus VectGen, který nahrazuje tři parametry jedním. Jedná se o vzdálenost mezi vertexem 2 a spojnicí vertexů 1 a 3, jedná se o analogii s pásmovými algoritmy. Lokální trojbodové algoritmy jsou rychlé ale jejich efektivita se zhoršuje s nehomogenitou linie a velikostí tolerance. Z toho důvodu jsou zvláště vodné k iniciální homogenizaci (odstranění chyb samplování, kde za testovanou vzdálenost volíme maximální dosažitelnou přesnost digitalizace) a v kombinaci se segmentačními algoritmy. stanovíme minimální výšku mikro-oblouku začínáme prvním vertexem a testujeme následující vertex oproti spojnici poslední fixovaný vertex, následující vertex od testovaného pokud podmínku splňuje fixujeme ho pokud ne vypustíme ho následující vertex se stává testovaným Automatizovaná kartografická generalizace 47 Filtrace Langův algoritmus Tento jednoduchý lokální algoritmus navrhl Lang v 1969. Jeho základním principem je odhad fixovaného vertexu. Tato vlastnost z něho stále dělá použitelný algoritmus. Odhad fixovaného vertexu na jednu stranu urychluje algoritmus ale na druhou stranu potenciálně fixuje i nepotřebné vertexy definujeme vertexový krok (který vertex v pořadí od počátečního se bude testovat) a pásmovou toleranci zkonstruujeme spojnici mezi počátečním vertexem a vertexem odpovídající pořadí kroku pokud všechny mezilehlé vertexy leží ve vzdálenosti menší než pásmová vzdálenost vertex fixujeme a stane se novým počátečním bodem pokud některý z vertexů leží mimo pásmovou vzdálenost couvneme o jeden vertex a opět testujeme pásmo Automatizovaná kartografická generalizace 48 Filtrace Visvaligam a Whyatt algoritmus navržen v roce 1993, obrácením logiky DP algoritmu s využitím trojbodového mechanismu. Algoritmus funguje velice dobře na plošné objekty a zvláště na nespecifických umělých objektech. Index ho předurčuje pro implementaci v elektronických mapách. Je rychlý a topologicky robustnější než DP. Zcela jistě se jedná o jeden z nejlepších obecných algoritmů pro filtraci. pro každý mezilehlý vertex se vypočte plocha trojúhelníka definovaného jeho sousedními vertexy identifikujeme nejmenší trojúhelníky a jejich vertex odstraníme a přiřadíme mu index rovnající se ploše trojúhelníka přepočítáme nově definované trojúhelníky pro sousední vertexy právě oindexovaného vertexu opakujeme dokud neoindexujeme všechnu vertexy, pro správnou funkci filtrovacího indexu nesmí být žádný index nižší než poslední přiřazený před ním, pokud nastane takový případ Automatizovaná kartografická generalizace 49 Filtrace Sinuositou řízený filtr Navržený Duttonem je dalším příkladem lokálního polyvertexového filtru. Jeho principem je fixace vertexů v zakřivených částech linie. S ohledem na způsob selekce se opět jedná o vícenásobně použitelný filtrační index a tím je tento algoritmus vhodný pro elektronické mapy. definujeme vertexový krok k pro každý bod spočítáme rozdíl mezi regionální sinusoitou (poměr mezi délkou linie od vertexu -k do vertexu +k a délkou přímé spojnice vertexů -k, testovaný vertex, +k) a lokální sinusoitu (k=1) vypustíme vertexy s malou diferencí sinusoity fixujeme vertexy s velkou diferencí sinusoity Automatizovaná kartografická generalizace 50 Filtrace Kombinatorická filtrace Jedná se o celou třídu algoritmů, které jsou založeny na minimalizaci zvoleného parametru (např. celková délka, úhlové změny, kolmé vzdálenosti původních vertexů, vymezená plocha). První komplexní diskuse tohoto přístupu v Cromley a Campbell [1992]. Zajímavá je modifikace DP algoritmu kde body nejsou vybírány podle extrémní vzdálenosti ale podle minimalizace kolmé vzdálenosti mezilehlých vertexů k definovaným vodícím čarám. Algoritmy tohoto typu poskytují dobré výsledky ale jsou značně pomalé. identifikujeme všechny testovatelné vertexy stanovíme testovací kritérium porovnáme výsledky všech variant a vybereme nejlepší vertex opakujeme dokud máme vertexy na testování Automatizovaná kartografická generalizace 51 Filtrace Douglas-Peuckerův algoritmus Tento nejrozšířenější pásmový filtrační algoritmus byl navržen Douglasem a Peuckerem v 1973 (nicméně podobný algoritmus navrhl v oblasti zpracování signálu Ramer aniž by to uvedeným autorům bylo známo). Algoritmus byl mnohokrát hodnocen a srovnáván a bylo konstatováno, že patří k nejefektivnějším filtračním algoritmům (Staněk 2000). Bylo zjištěno, že výběr kritických vertexů je obdobný manuálnímu výběru (Beard 1991). Jeho indexovaná forma je základem mnoha návrhů na hierarchický systém liniových objektů (vanOosterom 1995, Cromley 1991 a Buttenfield 1985). Existují také četné pokusy o jeho optimalizaci (např. Saalfeld 1998, který urychluje výběr vertexů pomocí konvexního obalu) . Základním problémem tohoto algoritmu je sklon k hrotovitosti (sousední hrany svírají příliš ostrý úhel a splývají) je proto vhodné kombinovat ho s nějakým zhlazujícím algoritmem. definujeme pásmovou toleranci spojíme koncové vertexy kotevní linií odstraníme všechny vertexy s kolmou vzdáleností menší než pásmová tolerance a identifikujeme nejvzdálenější vertex mimo pásmo (tento krok lze v první, případně druhé iteraci vypustit) identifikujeme nejvzdálenější vertex mimo pásmo (případně pro každou stranu od kotevní linie) vytvoříme nové kotevní linie procházející vybraným vertexem a pokračujeme pro vytvoření indexu vertexy neodebíráme, identifikovaným bodům přiřadíme index rovnající se vzdálenosti ke kotevní linii, pro konzistenci indexu se zavadí stejné pravidlo jaké bylo uvedeno u algoritmu Visvalingam-Whyatt. Automatizovaná kartografická generalizace 52 Zjednodušení Krokovací algoritmus Další z významných lokálních algoritmů uvedený Müllerem 1987, tento algoritmus využívá fraktality liniových prvků - délka v hranice přírodního jevu je závislá na měřící jednotce. Jednou z uváděných nevýhod tohoto algoritmu je, že nezjistí prvky, které jsou menší než dvojnásobek délky kroku. Jeho hlavní využití je v porovnávání zkreslení délek po generalizaci - srovnáváme délku linie před a po generalizaci, když na obě aplikujeme krokovací algoritmus s krokem o velikosti nejmenšího viditelného objektu cílového měřítka. definujeme délku kroku od počátečního vertexu kráčíme po linii v místě průniku definujeme nový vertex a kráčíme dokud je možný průnik s linií nakonec přidáme poslední vertex aby se algoritmus dal použít k filtraci je nutná úprava - místo průniku fixujeme nejbližší existující vertex od průniku Automatizovaná kartografická generalizace 53 Zjednodušení Algoritmus Whirlpool Navržený Dougenikem 1980 je nejjednodušší a nejefektivnějším algoritmem perkalovského typu. Princip algoritmu je nahrazení shluku blízkých vertexů jejich centroidem. Algoritmus podává velmi dobré výsledky a produkuje v perkalovském smyslu korektní linie. Problémem je nemožnost detekce koalescence vertexu a hrany. definujeme toleranci všem vertexům definujeme obal o velikosti zadané tolerance, všechny vertexy jejichž obal se proniká tvoří shluk, pokud mezi dvěma vertexy s pronikajícím se obale leží vertexy přiřadí se také do shluku shluky se nahradí jejich centroidem Automatizovaná kartografická generalizace 54 Zjednodušení Iterativní generalizace oblouků Tento algoritmus popsaný Wangem a Müllerem 1998 je implementován v systému ArcGIS jako BENDSIMLIFY funkce. Iterativnost metody je v dána vznikem nových oblouků po odstranění méně významných. Oblouky nejsou zcela korektní protože nezačínají v inflexních bodech. detekce oblouků pomocí rozdělením linie na pozitivní a negativní oblouky pomocí série úhlů svíraných hranami (pozitivní segment svírá úhel > 180 º) vypočteme index kompaktnosti pro každý oblouk (zvolíme parametry oblouky jako základna, délka apod.) postupně odstraníme nejméně významné ohyby Automatizovaná kartografická generalizace 55 Zjednodušení (Typifikace) Nejlépe orientovaný pravoúhelník stejné velikosti Tato metoda definovaní Hangouëtem v 1996 slouží především ke generalizaci budov. Jedná se o poměrně jednoduchou metodu která ale dává poměrně efektivní výsledky. Určíme směr budovy na základě převažujícího směru jejích stěn Narotujeme budovu tak aby její směrnice byla rovnoběžná s přilehlou hlavní osou Sestrojíme MBR Orotujeme MBR zpět Automatizovaná kartografická generalizace 56 Zvýraznění Škálování Proporcionální zvětšení nebo zmenšení tvaru. Tento transformační mechanismus je implementován v každém GIS software. Z hlediska algoritmického postupu je jen nutné udržet polohu objektu. Určíme centroid objektu pomocí MBR Škálujeme objekt Určíme MBR centroid nového objektu a posuneme ho tak abychom ztotožnili centroidy Automatizovaná kartografická generalizace 57 Zvýraznění Balón Lecordix a Plazanet, 1996. Tento algoritmus se snaží odstranit auto-koalescenci. určíme odsunutí o, zahušťovací krok h identifikujeme auto-koalescentní oblouk, provedeme jeho zahuštění kolmo k ose oblouku posouváme proporcionálně vertexy tak, že maximum o je u sousedů vrcholu a nulový posun je u základny Automatizovaná kartografická generalizace 58 Zhlazení Klouzavý průměr V kartografii poprvé použil McMaster v roce1989 Stanovíme look = počet sousedů po obou stranách vertexu a husf = největší velikost hran pokud husf je větší než 0 přidáme virtuální vertexy tak aby hrany nebyly větší než husf zachováme první vertex všechny původní vertexy nahradíme průměrem jich samých a jejich sousedů ( včetně virtuálních) v rozmezí definovaném look faktorem. Pokud look faktor přesahuje rozsah vertexů křivky, omezíme se na této straně jen na existující vertexy. zachováme poslední vertex Automatizovaná kartografická generalizace 59 Zhlazení Gaussovo zhlazování Jeden z nejlepších zhlazovacích algoritmů zavedený Badaudem 1986. Používá se i pro identifikaci oblouků. stanovíme sigma (násobek 4 sousedů po obou stranách vertexu) a husf = největší velikost hrany pokud husf je větší než 0, přidáme virtuální vertexy tak aby hrany nebyly větší než husf zachováme první vertex všechny původní vertexy nahradíme součtem jich samých a jejich sousedů ( včetně virtuálních) v rozmezí definovaném sigma faktorem, přičemž každý bod je opatřen vahou odpovídající normálnímu rozdělení ( posouvaný bod leží ve vrcholu rozdělení). Pokud faktor přesahuje rozsah vertexů křivky, připočteme k váze odpovídajícího vertexu váhy přesahujících bodů. zachováme poslední vertex Automatizovaná kartografická generalizace 60 Zhlazení Brophyho zhlazování Navrhl Brophy v roce 1973, velmi dobrý zhlazovací algoritmus a navíc jeho inverze (vertexy se místo přibližování oddalují) lze využít ke karikatuře stanovíme look = počet sousedů po obou stranách vertexu husf = největší velikost hrany smoof = faktor posuvu vertexu na intervalu 0..1 pokud husf je větší než 0, přidáme virtuální vertexy tak aby hrany nebyly větší než husf zachováme první vertex všechny původní vertexy nahradíme bodem ležícím na spojnici těchto vertexů se středy vepsaných trojúhelníku definovaných daným vertexem a jeho sousedy po obou stranách ve vzdálenosti look ( pokud look přesahuje křivku použijeme odpovídající nod). Umístění bodu na spojnici je určeno smoof parametrem. zachováme poslední vertex Automatizovaná kartografická generalizace 61 Odsazení Proporcionální radiální expanze Navrhl Mackaness v roce 1994. Cílem je snížit nahloučení skupiny bodových objektů (nebo plošných přibližně stejné velikosti) jejich expanzí. vyberte středu clusteru přesun všech bodů od středu do vzdálenosti úměrná původní vzdálenost od centra v tomto bodě pokud algoritmus produkuje topologické chyby pozice středu musí být změněny Automatizovaná kartografická generalizace 62 Odsazení Symetrické odsazení Poměrně jednoduchý algoritmus na odsazení dvou objektů sestrojte opsané kružnice obou objektů sestrojle přímku procházející jejich středy osuňte objekty jejich středem po přímce tak aby se opsané kružnice neprotínaly Automatizovaná kartografická generalizace 63 Agregace Amalgamace pomocí delaunayovi triangulace Jednoduchý systém amalagamace podle Jonese z roku 1989 definujte MBR amalgamovaných objektů generujte delaunayovu síť odstraňte trojúhelníky, které mají vrchol na MBR sjednoťte ostatní trojúhelníky Automatizovaná kartografická generalizace 64 Agregace Amalgamace pomocí matematické morfologie Navrhl Staněk v roce 1999 jako vektorovou analogii k algoritmu navrženému Li pro rasterovou generalizaci. Algoritmus je citlivý na volbu velikosti bufferu. definujte velikost bufferu sjednoťte buffery amalgamovaného shluku odečtěte od výsledného tvaru buffer stejné velikosti proveďte zjednodušení získaného tvaru Uvedené algoritmy jsou často pouze interpretací neurčitého popisu. Proto neuvádím u této kapitoly reference. Pokud je znám autor algoritmu je to uvedeno v textu. Automatizovaná kartografická generalizace 65