Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- mgr-szz:in-gra:11-gra [2016/06/05 10:13]
haf [Zadání]
+++ mgr-szz:in-gra:11-gra [2020/04/12 16:56]
@@ Řá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).
-======
-uktury 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.
-====== Metoda přímého přístupu ======
-//Není mi zřejmé, co přesně je zde myšleno. Vzhledem k tomu, že tato část otázky byla vypuštěna pro státnice od r. 2014, snad to ani není moc důležité. V knize Moderní počítačová grafika ani ve slajdech k předmětu Počítačová grafika není k tomuto tématu nic uvedeno. Snad toto. Popisuje obecná data, ale lze si představit i jako strukturu pro popis scény objektů.//
-===== Přímý přístup k datům =====
-Pod přímým přístupem k datům se rozumí přímé čtení záznamu ze známé adresy. V těchto metodách se každý požadovaný záznam se přečte hned napoprvé. Metody přímého přístupu k datům evidentně vyžadují znalost adresy pro každý záznam. To neznamená, že v každém okamžiku jsou známy adresy všech záznamů najednou. Znamená to, že v okamžiku potřeby daného záznamu existuje možnost adresu zjistit. U těchto metod se obdobně jako u metod sériového hledání předpokládá existence klíče a vzestupné nebo sestupné uspořádání jeho hodnot.
-==== Přímé adresování ====
-Při metodě přímého adresování je adresou přímo klíč nebo jeho lineární transformace. Metoda přímého adresování je vhodná v případě, že
-  * klíč je numerický
-  * ke každé hodnotě klíče z nějakého uzavřeného intervalu existuje záznam
-  * délka záznamu je u všech záznamů stejná
-**Příklad**: Nechť každý z 13 vrtů v terénu má číselný kód od 1 do 13 (vrty jsou tedy "očíslovány"). Nechť délka záznamu obsahující údaje o každém vrtu je 67. Klíčem vrtu je jeho číslo -v- a z něj lze odvodit adresu záznamu výrazem A = (v-1) * 67.
-==== Nepřímé adresování ====
-Nejčastěji však data v souborech nesplňují ani přibližně požadavky odůvodňující přímé adresování. Je to např. tehdy, když
-  * posloupnost klíčů ani teoreticky neobsahuje všechny hodnoty jediného uzavřeného intervalu, ale mezi hodnotami jsou "velké mezery".
-  * klíč je koncipován tak, že teoreticky umožňuje použít všechny hodnoty z nějakého uzavřeného intervalu, ale je známo, že všech skutečných záznamů bude mnohem méně.
-  * klíčem je výraz jiného typu než numerického a nemůže tedy být přímo použit k adresování.
-V uvedených a podobných případech je nutno mít k disposici funkci, která transformuje hodnotu klíče na adresu. Adresa není tedy určena přímo, ale zprostředkovaně klíčem; proto se tyto metody nazývají metody nepřímého adresování, a protože používají (již při výkladu metod zápisu zmíněnou) Hash - funkci, nazývají se také Hash - metodami.
-Zpravidla není možno sestrojit funkci A = A (k) tak, aby to bylo prosté zobrazení (celé) množiny klíčů na rovnoměrně rozložené adresy v množině použitelných adres. Na druhé straně by funkce A neměla být (z časových důvodů při jejím vyhodnocování) příliš složitá. Proto se užívají takové funkce, které některé adresy ponechávají neobsazené a jiné adresy jsou obrazem většího počtu klíčů.
-===== 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.

mgr-szz/in-gra/11-gra.txt · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)

Nahoru