BLG-strom (Binary Line Generalization Tree), je novou datovou strukturou s úrovněmi detailů. Nejprve popíšeme, proč je nutná generalizace linií, proč je v dosavadních strukturách nedostatečná a dále seznámíme se samotným BLG-stromem.
Když má být zobrazena mapa malého měřítka, tak se vyberou pouze důležité polylinie (či polygony) ze souboru dat velkého měřítka. Tyto polylinie jsou ale stále vykresleny s příliš mnoha detaily, protože se používají všechny body, které definují danou polylinii. Tyto detaily budou ve výsledku ztraceny kvůli limitujícímu rozlišení obrazovky a jejich vykreslování zabere zbytečný čas. Proto je lepší použít méně bodů. K tomu lze použít například algoritmus k-tého bodu (k-th point algorithm). První a poslední bod polylinie je v tomto algoritmu vždy zachován. To je důležité kvůli zachování připojení k dalším vrcholům. Tento algoritmus může být vykonán za běhu, protože je velmi jednoduchý. Nastavení k-tého bodu může být závislé na aktuálním měřítku. Tato metoda má bohužel i své nevýhody:
Tvar polygonu nemusí být optimálně reprezentován. Některé charakteristiky linie mohou být ztraceny, zvláště pokud originální polylinie obsahuje velmi ostré ohyby, nebo dlouhé liniové úseky.
Pokud máme dvě sousedící administrativní jednotky a použijeme tento algoritmus na každou z nich, polygony pak na sebe nemusí pasovat. (Uvažujeme, že obrys obsahuje přepočtené body několika polylinií.)
Proto musí být použit lepší generalizační algoritmus. Například Douglas-Peuckerův algoritmus. [1] Tyto algoritmy jsou ale časově náročné, a proto je vhodné dopředu spočítat generalizovanou informaci pro každou polylinii. Výsledek může být uložen například v multi měřítkovém liniovém stromu.
Strip strom a Arc strom jsou binární stromy reprezentující křivky v hierarchickém uspořádání se zvýšenou přesností v nižších úrovních stromu. Tyto datové struktury jsou vytvořeny pro libovolné křivky a ne pro jednoduché polylinie. Proto zde uvádíme novou datovou strukturu, BLG-strom.
BLG-strom vychází z Douglas-Peuckerova algoritmu pro binární strom. [1] Původní polylinie se skládá z bodů p1 až pn. Nejhrubší aproximací této polylinie je liniový úsek [p1, pn]. Chyba této aproximace je dána nejvíce vzdáleným bodem originální polylinie od aproximované linie. Předpokládejme, že je to například bod pk se vzdáleností d. pk a d jsou uchovány v kořeni BLG-stromu, který reprezentuje liniový úsek [p1, pn]. Další aproximace je tvořena dvěma liniovými úseky [p1, pk] a [pk, pn]. Kořen BLG-stromu obsahuje dva ukazatele na uzly, které odpovídají těmto liniovým úsekům. Pro běžný případ je tato reprezentace přesnější.
K liniovým úsekům [p1, pk] a [pk, pn] se můžeme chovat stejně jako liniovému úseku [p1, pn] celé polylinie. Opět chyba liniového úseku může být udána nejvzdálenějším bodem a opět bod a tato vzdálenost budou uchovány v uzlu, který reprezentuje daný liniový úsek. Tento proces se opakuje, dokud nejsou všechny body uloženy v BLG-stromu. BLG-strom tedy připojuje přesnou reprezentaci originální polylinie.
![Polylinie a BLG-strom (v kulatých závorkách je uvedena chyba). [1]](resources/13_Polyline_and_BLG.png)
BLG-strom je statická struktura s ohledem na vkládání, mazání a změnu bodů, které definují polylinii. Polylinie a BLG-strom jsou zobrazeny na obrázku 13. Při sestupování stromem budou ve většině případů hodnoty vzdálenosti uchované v uzlech menší. Bohužel to není vždy pravidlem, jak ukazuje obrázek 14.
BLG-strom se používá během zobrazení polylinie při určitém měřítku.
Dále může být využit při:
odhadování plochy oblasti uzavřené skupinou polylinií
odhadování průniků dvou polylinií
(To je užitečná operace během výpočtu mapového (polygonového) překrytí.
![Rostoucí chyba v BLG-stromu. [1]](resources/14_Increasing_Error_BLG.png)