Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
Následující verze | Předchozí verze | ||
mgr-szz:in-gra:11-gra [2013/06/13 16:44] bobas vytvořeno |
mgr-szz:in-gra:11-gra [2016/06/14 16:30] haf |
||
---|---|---|---|
Řádek 1: | Řádek 1: | ||
+ | ====== Zadání ====== | ||
+ | Datové struktury pro prostorové vyhledávání. Vyhledávání podle rozsahů, multidimenzionální binární stromy, stromy úseček. | ||
+ | |||
+ | (Staré znenie:) | ||
+ | Datové struktury pro prostorové vyhledávání. Vyhledávání podle rozsahů, multidimenzionální binární stromy,metoda přímého přístupu, stromy úseček. Sjednocení a průniky obdélníků. | ||
+ | |||
+ | Pozn.: některé matematické základy poskytují poznámky z předmětu Geometrické algoritmy (viz Použité zdroje). | ||
+ | |||
+ | ====== Datové struktury pro prostorové vyhledávání ====== | ||
+ | ===== Příklady elementárních úloh ===== | ||
+ | * Lokalizace bodu v 2-3D prostoru - hledání objektu, kterému patří daný bod | ||
+ | * Hledání nejbližších n bodů od daného středu - globální varianta: hledání nejbližší dvojice bodů | ||
+ | * Zpracování objektů podle vzdálenosti od středu | ||
+ | * Hledání průsečíku na množině úseček (křivek) | ||
+ | * Hledání nejbližšího průsečíku s 3D scénou | ||
+ | * Intervalové dotazy v 2-3D prostoru | ||
+ | * Windowing problém - ořezávání úseček podle předem zadaného polygonálního okna | ||
+ | * Množinové operace nad mapovými objekty - oblasti, linie, bodové objekty | ||
+ | * Testy kolizí a minimálních vzdáleností mezi objekty | ||
+ | |||
+ | ===== Ortogonální vyhledávání – motivace ===== | ||
+ | Máme databázi pracovníků firmy, která obsahuje následující údaje pro každého zaměstnance: délku zaměstnání, plat, nemocnost, počet prohřešků. Dva z těchto údajů si můžeme představit jako souřadnice bodů ve dvourozměrném prostoru: | ||
+ | |||
+ | {{:mgr-szz:in-gra:11_html_m8a69e38.jpg|}} | ||
+ | Každý bod představuje jednoho pracovníka. Vyhledávání je dáno **obdélníkem** [x, x'] * [y, y']. | ||
+ | |||
+ | ===== Binary Space Partition trees ===== | ||
+ | BSP stromy jsou binární stromy sloužící k prostorovému třídění scény obecně v n rozměrném prostoru . Celá scéna je rekurzivně dělena nadrovinou . Listy BSP stromu odpovídají konvexnímu rozkladu scény. Prostor určený jedním listem obsahuje maximálně jeden objekt (případě zlomek objektu). | ||
+ | |||
+ | |||
+ | {{:mgr-szz:in-gra:11_html_465110c7.jpg|}} | ||
+ | Tvoří se rekurzivně dokud množina objektů obsahuje více než jeden objekt. | ||
+ | |||
+ | Dělicí nadroviny mohou být libovolné nebo pouze ortogonální (= snazší zpracování, ale může mít menší schopnost rozdělit scénu = je potřeba více dělení). | ||
+ | |||
+ | ==== Využití ==== | ||
+ | === Malířův algoritmus === | ||
+ | Malířův algoritmus rekurzivně prochází stromem. Pokud je uzel listem, vykreslí ho, jinak rekurzivně vykresluje větve – nejprve vzdálenější. | ||
+ | |||
+ | === Detekce kolizí === | ||
+ | Pokud máme BSP strom scény a chceme detekovat kolizi nového tělesa, stačí zjistit, které listy BSP stromu nový objekt protíná a zde otestovat kolizi (s jedním tělesem). | ||
+ | |||
+ | ===== Quad strom ===== | ||
+ | Speciální případ BSP stromu. | ||
+ | |||
+ | Dělí prostorovou scénu pouze v ortogonálních směrech. Rozšířením quad stromu z dvourozměrného do třírozměrného prostoru jsou tzv. **oct** strom. Informace o objektech uloženy v listech. | ||
+ | |||
+ | {{:mgr-szz:in-gra:11_html_5091ff20.jpg|}} | ||
+ | ==== Využití ==== | ||
+ | Lokalizace bodů – point region. | ||
+ | |||
+ | {{:mgr-szz:in-gra:11_html_m1afa0b1c.jpg|}} | ||
+ | ===== Quad strom s kbelíkem („bucket“) ===== | ||
+ | V jednom listu (uzlu) se ukládají údaje o **několika objektech **pro zmenšení spotřeby paměti i času přístupu – menší režie na údržbu ukazatelů. | ||
+ | |||
+ | {{:mgr-szz:in-gra:11_html_mfe5fcd4.jpg|}} | ||
+ | ===== kD (k-dimenzionální) strom ===== | ||
+ | Speciální případ BSP stromu. Více dimenzionální vyvážený binární vyhledávací strom provádějící dělení střídavě podle x-ové a y-ové souřadnice (ve 2D). | ||
+ | |||
+ | |||
+ | {{:mgr-szz:in-gra:11_html_m2ced505f.jpg|}} | ||
+ | Region odpovídající uzlu //v// (//region(v)//) je obdélník, který může být neomezený v jednom nebo více směrech. | ||
+ | |||
+ | * Region kořenu kD-stromu je celá rovina | ||
+ | * Bod je uložen v podstromu uzlu //v// právě tehdy, jestliže leží v regionu //region(v)//. | ||
+ | * Podstrom uzlu //v// prohledáváme pouze tehdy, jestliže //region(v)// má neprázdný průnik s dotazovaným obdélníkovým rozsahem. | ||
+ | * Jestliže je //region(v)// zcela obsažen v dotazovaném rozsahu, můžeme nahlásit všechny body celého podstromu //v//. | ||
+ | |||
+ | Prohledávání probíhá rekurzivně po větvích – pokud je zkoumaný uzel listem a odpovídá regionu, je nahlášen, jinak se zkoumají větve – pokud je větev celá v rozsahu, je nahlášena, pokud rozsah protíná, je rekurzivně zkoumána. | ||
+ | |||
+ | ===== Rozsahový strom (range tree) ===== | ||
+ | Range tree je složen z jednoho binárního vyváženého stromu T, jehož listy jsou body množiny P v rovině seřazené podle x-ové souřadnice. (Předpokládáme, že každé dva body mají různé souřadnice x a y). Uzly stromu jsou ohodnoceny nejvyšším číslem své levé větve. Rozsahový strom pro d-dimenzionální body množiny P je rekurzivně definovaný víceúrovňový binární vyhledávací strom. Každá jeho úroveň je binární vyhledávací strom na jedné z d dimenzí. První úrovní je binární vyhledávací strom na první z d souřadnic. Každý vrchol v tohoto stromu obsahuje asociovanou strukturu, která je d-1 dimenzionálním stromem na posledních d-1 souřadnicích bodu uloženého v podstromu v. | ||
+ | |||
+ | {{:mgr-szz:in-gra:11_html_m3be12a9.jpg|}} | ||
+ | Strom se stejnými listy jako podstrom v T, ale uspořádanými podle souřadnice y. | ||
+ | |||
+ | Např. pro 3 dimenze: | ||
+ | |||
+ | {{:mgr-szz:in-gra:11_html_m4c5acfe4.jpg|}} | ||
+ | Vyhledávání rozsahů (regionů) probíhá nejprve podle první souřadnice, při nalezení správného rozsahu (který obsahuje list v), pokračuje postupně podle dalších souřadnic, jejichž stromy jsou uloženy asociovaně k uzlu v. | ||
+ | |||
+ | ===== Hledání v datech s indexy ===== | ||
+ | //Toto je uvedeno navíc – otázka se na toto neptá, ale tak pro doplnění a rozšíření metody přímého přístupu. Protože jinak tam není moc o čem mluvit...// | ||
+ | |||
+ | Tyto metody hledání mohou být aplikovány pouze na soubory dat, ke kterým byly vytvořeny indexové tabulky (viz odstavec o metodách uložení s indexy). Protože indexové tabulky jsou vytvářeny na základě hodnot klíčů, je možno hledat záznam pouze podle kriteria, kterým je hodnota klíče. | ||
+ | |||
+ | Při této metodě se hledání ve vlastním souboru dat převádí na hledání dané hodnoty klíče v indexové tabulce. Po nalezení záznamu indexové tabulky je z pole adresy získána adresa datového záznamu v souboru dat, a tento záznam se pak přímo získá jediným čtením. | ||
+ | |||
+ | Pro hodnocení metod hledání v datech s indexy platí vše, co bylo uvedeno dříve, ovšem aplikováno na soubor indexů. Organizace uložení v souboru indexů tedy určuje efektivitu používání souborů s indexy. Protože z dosud hodnocených metod hledání je nejméně efektivní sekvenční metoda, téměř nikdy se nepoužívá ani sekvenční organizace uložení, ani sekvenční hledání. | ||
+ | |||
+ | Velmi často se pro indexová tabulky používá uložení s odkazy. Záznam pak má 6 polí: čtyři pole s odkazy (na předchůdce, následovníka, a na levého a pravého souseda), jedno pole pro hodnotu klíče a jedno pro hodnotu adresy záznamu. Indexová tabulka pak má tvar stromu (z teorie grafů). Každý záznam je pak jedním uzlem v tomto grafu, hrany grafu jsou obrazem odkazů. Výhodou je možnost ukládat v každém uzlu ne kompletní hodnoty klíče, ale jen část hodnoty klíče náležející dané úrovni uzlu v grafu. | ||
+ | |||
+ | ====== Stromy úseček (Segment trees) ====== | ||
+ | Stromová datová struktura pro uložení intervalů (úseček). Dovoluje dotazování, která úsečka odpovídá specifikovanému bodu. Principiálně statická struktura – obsah nemůže být měněn, pokud byl jednou strom sestaven. | ||
+ | |||
+ | Strom úseček je binární vyhledávací strom sestaveny nad množinou koncových bodů úseček. Koncové body dělí výchozí interval (-∞; ∞) na disjunktní elementární intervaly. Každý list stromu odpovídá jinému elementárnímu intervalu. Vnitřní vrcholy odpovídají **sjednocení **intervalů svých větví. Vrcholy obsahují pole přiřazených intervalů bez těch, které jsou již přiřazeny v jejich rodičích. | ||
+ | |||
+ | {{:mgr-szz:in-gra:fig198_01.jpg|}} | ||
+ | Segmentový strom můžeme dále „vylepšit“, aby mohl obsahovat i body (úsečky nulové délky – intervaly [p; p]) a rozlišovat uzavřené a otevřené intervaly tak, že do množiny intervalů přidáme intervaly [p; p] pro každý bod p množiny koncových bodů: | ||
+ | |||
+ | {{:mgr-szz:in-gra:8039f9d2875aea07fe90546a97427737.png|}} | ||
+ | {{:mgr-szz:in-gra:segment_tree_instance.gif|}} | ||
+ | |||
+ | Koncept segmentových stromů lze zobecnit i do vyšších dimenzí, na rozdíl např. od intervalových stromů. Intervalové stromy ale mají menší paměťovou náročnost, takže může být vhodné budovat hybridní strom, který je ve vyšších úrovních segmentový a v nižších intervalový. | ||
+ | |||
+ | ====== Sjednocení a průniky obdélníků ====== | ||
+ | //Opět není jisté, čeho se týká. Zřejmě jde o sjednocení a průniky obdélníků (= regionů) při vyhledávání ve více-dimenzionálních datech, tedy něco jako vyhledávání v databázi s SQL dotazem WHERE ... AND ... resp. WHERE ... OR ... . Ovšem ani k tomu nikde žádné relevantní informace nejsou.// | ||
+ | |||
+ | Regiony dotazu v prostorovém vyhledávání jsou obdélníky výsledků. Např. v tomto dotazu: | ||
+ | |||
+ | {{:mgr-szz:in-gra:11_html_m8a69e38.jpg|}} | ||
+ | jsou výsledkem všichni zaměstnanci, jejichž délka zaměstnání je v rozmezí x – x' a mají plat v rozmezí y – y'. Pokud bychom chtěli vyhledávat s logickou podmínkou **or (nebo)**, obdržíme dva obdélníky, jejichž **sjednocením **je výsledek dotazu. Např. dotaz na zaměstnance, jejichž délka zaměstnání je v rozmezí x – x' a mají plat v rozmezí y – y' **nebo** jejichž délka zaměstnání je nejvíce x / 2, dostaneme následující odpověď: | ||
+ | |||
+ | {{:mgr-szz:in-gra:11_html_30c19b74.jpg|}} | ||
+ | Pokud bychom chtěli vyhledávat s logickou podmínkou **and (a zároveň)**, obdržíme dva obdélníky, jejichž **průnikem **je výsledek dotazu. (Smysluplný příklad ve 2D mě nenapadá, jelikož všechny dotazy na obdélníky s podmínkou **and** lze snadno přepsat na jeden dotaz. Např.: obdélník [x₁, x₁'] * [y₁, y₁'] **and **[x₂, x₂'] * [y₂, y₂'] lze přepsat jako [x, x'] * [y, y'], kde x = max(x₁, x₂), x' = min(x₁', x₂'), y = max(y₁, y₂), y' = min(y₁', y₂')) | ||
+ | Obě operace lze v uvedených datových strukturách realizovat pomocí nalezení regionů obou poddotazů a jejich sjednocením, resp. průnikem. Vyhledání by mohlo být také optimalizováno, aby neprocházelo dvakrát společné uzly stromů. | ||
+ | |||
+ | ====== Použité zdroje ====== | ||
+ | Josef Pelikán, Jiří Sochor : PB009 - Základy počítačové grafiky, slajdy. 2012. Fakulta informatiky, Masarykova Univerzita. Brno. | ||
+ | |||
+ | http://geologie.vsb.cz/geoinformatika/kap03.htm | ||
+ | |||
+ | http://en.wikipedia.org/wiki/Segment_tree | ||
+ | |||
+ | http://flylib.com/books/en/2.587.1.48/1/ | ||
+ | |||
+ | Ril: Geometrické algoritmy (PřF:M7130). 2011. https://is.muni.cz/auth/of/1431/M7130/podzim2011/geometricke_algoritmy.pdf. | ||