2. Úvod do reaktivních datových struktur

Představujeme reaktivní datové struktury. Reaktivní datové struktury jsou definovány jako geometrické datové struktury s úrovněmi detailů. Tyto struktury podporují relace (sessions). Pojem reaktivní datové struktury prvně představil Van den Bos v projektu IDECAP. Tyto struktury umožňují, aby informační systém reagoval okamžitě na uživatelem zadané akce, jako je například prezentování dat v určité oblasti s vhodným množstvím detailů. Je obtížné nalézt datovou strukturu, která by uspokojila všechny požadavky (r1 až r6) diskutované v předchozím oddílu. Ukazuje se, že kombinace požadavků r2 (prostorové schopnosti) a r3 (úrovní detailů) vytvářejí hlavní překážku. Nejprve se budeme soustředit na prostorové schopnosti r2. Vektorový formát se používá k uchovávání geometrických dat, jako jsou body, polylinie a polygony.

Nedostatky používání mapových kladů jsou v GIS dobře známé. Zřejmou odpovědí na tyto nedostatky je vytvoření bezešvé (seamless) databáze. Bezešvá databáze je možná v interaktivním prostředí za použití vhodné geometrické datové struktury. Některé z nejznámějších geometrických struktur budou popsány dále. Binární strom (B-tree) je z hlediska reprezentace prostorových dat nevhodný, protože geometrická data jsou vícedimenzionální. To samé se vztahuje k ostatním úložným strukturám, které jsou založené na jednodimenzionálním řádu, například zkosené stromy (splay trees). K uchování vztahů mezi těmito objekty je potřeba dalších struktur.

Druhý požadavek, na který je třeba brát zřetel, je zapojení úrovní detailů. Základem pro bezešvou a bezměřítkovou geografickou databázi je datová struktura s prostorovou organizací (spatial organization) a s úrovněmi detailů. Úrovně detailů musí být integrovány v prostorové organizaci dat. Řešení musí být nalezeno někde mezi následujícími body:

Reaktivní datová struktura je novým typem datové struktury, která podporuje vícenásobné úrovně detailů a odpovídá rychlou odezvou na geometrické dotazy. Tato struktura může být jak statická, tak dynamická. V položkách dynamických reaktivních datových struktur můžeme efektivně vkládat, mazat a aktualizovat, přičemž struktura zůstane vyvážená. V kapitole 4 Reaktivní strom rozdělující binární prostor bude navržen BSP strom (BPS-tree) spolu s první reaktivní datovou strukturou. V tomto případě se zatím bude jednat o statickou strukturu. Požadavkem r6 (dynamikou) se budeme zabývat až na závěr.