Vypracovane_otazky

ice je medián. Tento bod se vloží jako kořen a množina bodů se rozdělí na dvě části (větší než kořen a menší než kořen podle x-ové souřadnice). Algoritmus se dále aplikuje na oba podstromy, ale porovnává se podle souřadnice y. Souřadnice, podle které se porovnává, se v každém kroku mění.
5. Uveďte metodu Non-pointer Quad Tree (pevný kvartérní strom), indexování
prostorových objektů a konstrukce výběrové podmínky.
Území je rozděleno na obdélníkové části a podle jejich polohy je jim přidělen klíč.
Obdélník bude mít index takové dlaždice která je jeho nejmenší nadmnožinou. Při vyhledávání jsou na výstup posílány všechny obdélníky jejichž index začíná nenulovou částí indexu dotazového obdélníku a mají s dotazovým obdélníkem nenulový průnik. V následujících krocích se číslice klíče dotazového obdélníku zprava postupně nahrazují nulami a vyhledávání se opakuje (tzn. Vyhledává se o úroveň výš). V některých případech je prohledávaná oblast příliš velká, proto se dotazový obdélník dělí na menší části podle souřadnice, která způsobila klíčování.
6. Uveďte definici a základní principy budování SB+ stromů.
SB+ strom je B+ strom z počátečních a koncových bodů intervalů. V SB+ stromech jsou listům přidány seznamy intervalů, které jsou incidentní s klíčem v listu (tj. nějakým počátkem nebo koncem nějakého intervalu). S každým identifikátorem je pamatován příznak, který označuje zda se jedná o počáteční nebo koncovou hodnotu intervalu, popřípadě zda interval touto hodnotou prochází. Při vkládání intervalu se nejprve otestuje, zda strom již obsahuje počáteční pod nového intervalu. Pokud ne, tak se bod vloží standardní metodou pro B+ stromy a jako seznam intervalů listu se zkopíruje průnik seznamů bezprostředního předchůdce a následníka a všem intervalům se nastaví typ incidence na C. Postup se zopakuje i pro koncový bod vkládaného intervalu. Identifikace vkládaného intervalu se nakonec vloží i do všech bodů, kterými interval prochází.
7. Popište základní vlastnosti R-stromu (R-Tree) a zpracování prostorového dotazu
v něm.
Princip je založen na technice B-stromů. Každý uzel R-stromu obsahuje několik klíčů a ukazatelů na synovské uzly.
každý uzel obsahuje maximálně M a minimálně M/2 klíčů (pokud není kořen)
klíče v R-stromech jsou obdélníky s ukazateli na synovské uzly
v listech obdélníky s ukazateli na geometrické tvary
klíč synovského uzlu je uvnitř otcovského obdélníku
listy stromu jsou na stejné úrovni
kořen obsahuje minimálně dva klíče (pokud není list)
Vyhledávání incidentních obdélníků
1. Vstup uzel R-stromu R. Dotazový obdélník Q.
2. Je-li uzel list, tak všechny klíče incidentní s Q na výstup
3. Jinak aplikuj algoritmus na syny takových klíčů z uzlu, pro které je klíč incidentní s Q.
8. Popište metodu dělení uzlů v R-stromu (R-Tree) v lineární složitosti.
Vyber první dva obdélníky
Pro každou dimenzi najdi klíče s maximem minima a minimem maxima, stanov separační vzdálenost mezi těmito klíči (minimum - maximum)
Normalizuj separační vzdálenost tak, že vzdálenost intervalů podělíš rozsahem všech klíčů v dané dimenzi
Vyber dvojici k,l s největší normalizovanou separační vzdáleností, zařaď je do první a druhé skupiny
V případě, že jedna skupina obsahuje tak málo obdélníků, že pro zachování podmínky minima m musí obsahovat všechny nezařazené obdélníky, zařaď do ní zbývající obdélníky a konec
Vezmi další nezařazený klíč a zařaď jej do takové skupiny, jejíž MBR vyžaduje menší rozšíření.
9. Popište metodu dělení uzlů v R-stromu (R-Tree), v kvadratické složitosti.
Vyber první dva obdélníky
Pro každou dvojici klíčů k,l vytvoř minimální obdélník j obsahující oba klíče a polož p(k,l) = Plocha(j)-Plocha(k)-Plocha(l)
Vyber dvojici obdélníků k,l s maximem p(k,l), zařaď je do první a druhé skupiny.
V případě, že jedna skupina obsahuje tak málo obdélníků, že pro zachování podmínky minima m musí obsahovat všechny nezařazené obdélníky, zařaď do ní zbývající obdélníky a konec
Pro všechny nezařazené obdélníky spočítej rozdíl ploch o které se zvětší obdélníky první a druhé skupiny začleněním nezařazeného obdélníku.
Vyber obdélník z 3. který má maximální rozdíl ploch a zařaď ho do skupiny, jejíž celkový obdélník se rozšíří méně. Pokračuj krokem 2.
Okruh 3
1. Uveďte metodu, pomocí které zjistíme, zda je polygon orientován kladně i záporně.
Vyber ze všech hranic tu hranici a tři po sobě jdoucí body tak, aby prostřední bod měl minimální y (ze všech) a první měl y větší než prostřední. Otoč tak, aby orientovaná úsečka definovaná prvníma dvěma body ležela na x v kladném směru. Y-ová souřadnice posledního bodu určuje orientaci. (kladné y = kladná orientace)
2. Uveďte metodu, pomocí které určíme polohu bodu vůči úsečce.
Počátek souřadné soustavy přesuneme do počátku úsečky. Rotujeme úsečkou tak, aby ležela na ose X. Následnou polohu bodu lze určit přímo z jeho souřadnic.
3. Uveďte metodu, pomocí které určíme polohu bodu vůči polygonu resp. oblasti
(obecného areálu).
Najdi v bodech polygonu bod, jehož y-ová souřadnice je různá od souřadnice bodu, který testujeme. Jestliže neexistuje, ukonči proceduru s výsledkem LEŽÍ_NA_HRANICI. Nechť pp je polopřímka vycházející z testovaného bodu rovnoběžná s osou x v kladném směru.
nPrus:=0
Od vybraného bodu postupně procházej všechny úsečky a prověř body 4 – 7.
Leží-li testovaný bod na úsečce, ukonči proceduru s výsledkem LEŽÍ_NA_HRANICI.
Má-li úsečka vlastní průsečík s polopřímkou pp, potom nPrus:=nPrus+1
Končí-li úsečka na polopřímce a začíná-li mimo polopřímku, stanov podle počátku úsečky odkud:=POD nebo odkud:=NAD
Začíná-li úsečka na polopřímce a kon