3. Přehled prostorových datových struktur

Zde uvedeme velice stručný přehled doposud známých datových struktur a některé z nich blíže popíšeme. Jedná se o tři základní kategorie datových struktur: geometrická datová struktura, topologická datová struktura a datová struktura s úrovněmi detailů. Bereme v úvahu jen ty struktury, které vyžadují lineární množství úložného prostoru, protože vyšší požadavky vzhledem k objemu dat v GIS nepřipadají v úvahu. Pro zjednodušení budeme popisovat dvojdimenzionální varianty uvedených datových struktur, avšak většina z nich bude moci být použita i v třídimenzionálních aplikacích.

3.1. Geometrické datové struktury

Mezi geometrické datové struktury patří například KD-strom (KD-tree), čtyřstrom (Quadtree), konjugační strom (Conjugation tree), R-strom (R-tree), 2D uspořádání (Two dimensional orderings), grid (Grid file), strom polí (Field-tree) a strom s buňkami (Cell tree). V tomto oddíle ze zmíněných struktur přiblížíme alespoň R-strom.

Výzkum prezentovaný v [1] vyústil v další nové geometrické datové struktury: multi objektový BSP-strom (multi object BSP tree), generalizovaný KD-strom (generalized KD tree), KD2B-strom (KD2B-tree) a sférický strom (Sphere-tree). Z těchto struktur dále přiblížíme multi-objektový BSP-strom.

3.1.1. R-strom

R-strom je indexovaná struktura, kterou definoval Guttman v roce 1984. [1] Koncové uzly tohoto mnohacestného stromu obsahují položky ve tvaru: (I, identifikátor objektu), kde identifikátor objektu je ukazatel na datový objekt a I je ohraničující obálka, neboli osově souměrný minimální ohraničující obdélník (minimal bounding rectangle). Pro tento obdélník budeme používat zaběhlou zkratku MBR. Datový objekt může být libovolného typu: bod, polylinie nebo polygon. Vnitřní uzly (internal nodes) obsahují položky ve formě: (I, ukazatel na potomka), kde I je opět MBR toho potomka. Maximální počet položek v každém uzlu se nazývá faktor větvení M (the branching factor) a je vybrán tak, aby vyhověl stránkování a diskovému I/O buffering. Guttmanův algoritmus pro vkládání a mazání zaručuje, že počet položek v každém uzlu zůstane mezi m a M, kde m je minimálním počtem položek na uzel a platí, že m ≤ [M/2]. Výhodou R-stromu je, že jsou uchovány ukazatele k celým objektům (například polygonům). Důsledkem toho nejsou objekty nikdy fragmentované.

Obrázek 1. Geometrická datová struktura R-strom. [1]

Geometrická datová struktura R-strom. [1]

Obrázek 1. ukazuje R-strom se dvěma úrovněmi, kde M = 4. Nejnižší úroveň obsahuje 3 koncové uzly (listy) a nejvyšší úroveň obsahuje jeden uzel s ukazateli a MBR obdélníky koncových uzlů. Pokrytí (coverage) je definováno jako celá plocha všech MBR obdélníků koncových uzlů. Překrytí (overlap) je celá plocha obsažená ve dvou nebo více listech MBR. Pokrytí je tedy A∪B∪C a překrytí je A∩B. Je jasné, že efektivní vyhledávání vyžaduje jak nízké pokrytí, tak nízké překrytí  zabalený (packed) R-strom.

Roussopoulos a kolektiv popisují algoritmus „Pack“, jenž vytvoří počáteční R-strom, který je pak více efektivní, než kdyby tento R-strom byl vytvořen pomocí algoritmu vkládání. Algoritmus Pack často používá funkci nejbližší soused (nearest neighbour) v průběhu balení R-stromu. Může být použita funkce „City block distance“, protože je výpočetně levnější a vychází vstříc párům bodů (nebo MBR obdélníkům, které leží podél hlavní osy) místo diagonálním orientací. Výsledkem je vytvoření obdélníků s menším pokrytím.

R+-strom je modifikací R stromu, který se vyhýbá překrytí. Daní za to je ale více uzlů a vícenásobných odkazů k některým objektům, viz obrázek 2. Analytické výsledky ukazují, že R+-strom dovoluje efektivní vyhledávání v případě velkých objektů. Efektivnost R-stromu a R+- stromu byla porovnávána v paměťových datových strukturách. [1]

Obrázek 2. R+-strom. [1]

R+-strom. [1]

3.2. Topologické datové struktury

Geometrické datové struktury nejsou používány k explicitnímu uchovávání topologických dat. Pro tento účel je vytvořeno několik dalších datových struktur. S topologickou datovou strukturou by mělo být nakládáno v závislosti na tom, jak jsou používána geometrická primitiva (geometric primitives). Pokud jsou využívána k reprezentaci polygonů, pak by byla vhodná například struktura TIGER, vytvořená americkým úřadem pro sčítání lidu. Dalšími příklady topologických datových struktur jsou formální datová struktura (formal data structure), obrysová struktura (contour structure) a bodová struktura (point structure). Více viz [1].

3.3. Struktury s úrovněmi detailů

Začneme některými základními problémy, které se týkají úrovní detailů. Koncept vícenásobných úrovní detailů nemůže být definován stejně jednoduše jako prostorové vyhledávání. Je vztažen k jednomu z hlavních témat kartografického výzkumu a to k mapové generalizaci. V praxi to znamená odvodit mapu malého měřítka z mapy velkého měřítka. Bylo vyvinuto množství generalizačních technik pro geografické objekty:

  • zjednodušení (simplification) – například generalizace linií

  • spojení (combination) – geometrické nebo tematické seskupení

  • symbolizace (symbolization) – z polygonu na polylinii nebo na bod

  • výběr (selection) – eliminace, odstranění

  • zdůraznění (exaggeration) – zvětšení

  • přemístění (displacement) – posun

Mapová generalizace je na rozdíl od prostorového vyhledávání závislá na aplikaci. Generalizační techniky jsou děleny do dvou skupin: geometrická (geometric) a konceptuální (conceptual) generalizace. V případě geometrické generalizace zůstává základní grafická reprezentace objektů nezměněná, ale objekty mohou být například zvětšené. V případě konceptuální generalizace se reprezentace objektů mění, například změna řeky reprezentované polygonem na polylinii. Generalizace je komplexní proces, ze kterého jen některé části jsou vhodné k uskutečnění počítačem. Například generalizace linií je snadno uskutečnitelná počítačem, ale jiné techniky jsou více náročné. Velmi dobrých výsledků můžeme dosáhnout například při generalizaci map, které se skládají z lineárních prvků. Důležitou poznámkou je, že datové struktury s úrovněmi detailů jsou používány k uchování výsledků generalizace. Mezi tyto struktury patří, strip strom (Strip tree), arc strom (Arc tree), multi-měřítkový liniový strom (Multi-scale Line Tree) a Flintstones (Flintstones). Tyto struktury jsou vztaženy ke generalizaci linií a k aproximačním technikám. To samé platí o BLG-stromu, viz kapitola 5 Binární Liniově-generalizační strom.

3.3.1. Strip strom

Strip strom byl jednou z prvních datových struktur s úrovněmi detailů. Tento strom vytvořil Ballard v roce 1981. [1] Jedná se o hierarchickou reprezentaci křivek skládajících se z binárního stromu, kde každý uzel obsahuje obdélníkový pás (strip). Ukázka viz obrázek 3.

Obrázek 3. Strip strom. [1]

Strip strom. [1]

3.3.2. Arc strom

Arc strom je struktura podobná strip stromu a jedná se rovněž o binární strom, který reprezentuje hierarchicky chovající se křivku se zvýšenou přesností v nižších úrovních stromu. Hlavní odlišností od strip stromu je, že zde nejsou uchovávány žádné explicitní informace týkající se hraničního primitiva (bounding primitive) a způsobu, jakým je vybrán rozdělovací bod na křivce. Viz obrázek 4.

Obrázek 4. Arc-strom se zobrazenými pozicemi elips. [1]

Arc-strom se zobrazenými pozicemi elips. [1]

Pozn.: Uchovávány jsou pouze body, nikoliv elipsy. Elipsa E1 v levé části obrázku není zobrazena.

3.3.3. Multi-měřítkový liniový strom

Multi-měřítkový liniový strom je mnohacestný strom vhodný k reprezentaci polylinie pro pevný počet měřítek. Oproti arc stromu a strip stromu má tento strom kořeny více v kartografii než ve výpočetní technice. Je založen na Douglas-Peuckerově generalizačním algoritmu. Ten vybírá stejné body, jako by v požadovaném měřítku vybral strip strom pro polylinie, ale neukládá žádné obdélníkové pásy. Požadovaná měřítka musí být dopředu určena a pro každé měřítko je ve stromu jedna úroveň. Multi-měřítkový liniový strom znázorňuje obrázek 5.

Obrázek 5. Multi-měřítkový liniový strom. [1]

Multi-měřítkový liniový strom. [1]

3.3.4. Flintstones

Flintstones tvoří hierarchickou reprezentaci a aproximační schéma pro polygony. Existuje ve 2D i 3D variantě. První (zero-order) aproximací polygonu je minimální kružnice dotýkající se hranic objektu, která se dotýká minimálně dvou bodů originálního polygonu (viz obrázek 6a). Polygon je rozdělen na dvě polylinie, definované dotykovými body. Každá polylinie je uzavřena Flintstonem, což je nejmenší průnik dvou kruhů. Každá polylinie je rozdělena do dvou polylinií bodem, který se dotýká oblouku s největším zakřivením (viz obrázek 6b). Začátek, konec a dotykové body z první aproximace jsou vidět na obrázku 6c. Celý proces uzavírání polylinií Flintstonem se opakuje na další úrovni aproximace a je přirozeně reprezentován binárním stromem (viz obrázek 6d).

Výhodou Flintstones oproti arc stromu je lepší výběr rozdělovacích bodů a levnější sférický test oproti testu s elipsami. Nevýhodou je, že Flintstones nemusí být nutně vyvážený. Kvalitu bodů vybraných flintstonem a bodů vybraných strip stromem je těžké porovnat. [1]

Obrázek 6. Flintstones. [1]

Flintstones. [1]