Geometrické algoritmy

Pokud hledáme konvexní obal, pak můžeme postupně vyzkoušet všechny dvojice bodů $(p,q)$ a pro každou ověřit, že vlevo od ní (pomocí edge funkce) neleží žádný bod. Úsečky, pro které toto platí jsou poté součástí konvexního obalu.

Tento algoritmus je velice hloupý a má složitost $O(n^3)$, kde n je počet bodů.

Pro hledání konvexního obalu existují efektivnější algoritmy. Jeden z nich je postaven na principu hledání horní a dolní hranice konvexního obalu.

Seřadíme si všechny body podle vzrůstající souřadnice X. Poté řešíme horní a dolní obálku zvlášť. Oba algoritmy jsou obdobné, proto popíšu postup pouze pro horní obálku:

Pro horní obálku si vytvoříme prázdný zásobník. Postupně procházíme body a pro každý bod uděláme následující:

Tento algoritmus má složitost $O(n\log n)$, kde n je počet bodů.

Další algoritmus pro hledání konvexního obalu je tzv. gift wrapping (obalování dárku). Algoritmus je založen na tom, že postupně "obalujeme" body konvexním obalem.

Vybereme bod s nejmenší souřadnicí X a přidáme ho do konvexního obalu. Poté postupně procházíme všechny body a pro každý bod uděláme následující:

Tento algoritmus má složitost $O(nh)$, kde n je počet bodů a h je počet bodů v konvexním obalu. V nejhorším případě může mít složitost $O(n^2)$. Tento algoritmus je výhodný, pokud očekáváme, že konvexní obal bude mít málo bodů (méně, než $O(\log n)$).

Problém konvexního obalu ve 3D je výrazně komplikovanější (a popravdě se na FI ani v jednom předmětu neučí…​). Pro jeho konstrukci můžeme použít například algoritmus QuickHull [1].

Tento algoritmus má složitost $O(n\log n)$, kde n je počet bodů.

Oblast kolem každého bodu můžeme získat, jako průnik polorovin vytvořených přímkou uprostřed mezi tímto bodem a všemi ostatními body. Složitost nalezení jedné takové oblasti je $O(n\log n)$ (kvůli hledání průniku) a celková složitost je $O(n^2\log n)$.

Tento algoritmus je založen na postupném přidávání bodů (Doporučuji kouknout na toto video). Vybereme počáteční bod a postupně přidáváme body. Pro každý bod uděláme následující:

Tento algoritmus má složitost $O(n^2)$.

Další možností je rozdělit rovinu na dvě části a pro každou část udělat Voroného diagram. Poté spojit obě části pomocí společné hrany.

Poloviny určíme podle souřadnice X. Při spojování poté najdeme tzv separating chain. Všechny hrany z Vor(L) na pravé straně separating chain a všechny hrany z Vor® na levé straně separating chain zahodíme.

Separating chain vytvoříme následovně:

Tento algoritmus má složitost $O(n\log n)$.

Nejznámnějším algoritmem je Sweep Line. V algoritmu využíváme tzv. Beach line, což je křivka složená z parabol, která se nachází na sweeplinou.

Při pohybu sweepline může dojít ke dvěma druhům událostí:

Detailní popis algoritmu je na webu Geometrických algoritmů. Tento algoritmus má složitost $O(n\log n)$.

Pokud již máme k dispozici Delaunayovu triangulaci, můžeme snadno získat Voroného diagram. Stačí pro každů trojúhelník najít střed kružnice opsané a spojit středy těchto kružnic podle sousednosti trojúhelníků.

Můžeme zvolit libovolnou korektní triangulaci a poté se zbavit "ilegálních" hran tzv. lokální výměnou v zámci konvexních čtyřúhelníků.

Opakujeme, dokud dochází ke změnám: 1. Najdeme dva trojúhelníky, které tvoří konvexní čtyřúhelník a jejichž společná hrana je ilegální (kružnice opsaná libovolnému z těchto trojúhelníků obsahuje chybějící čtvrtý bod). 2. Legalizujeme tuto hranu (edge flip) (odstraníme ji a přidáme novou hranu mezi druhými dvěma body).

Tento algoritmus má složitost $O(n^2)$.

Další možností je inkrementální konstrukce. Iniciálně zvolíme jednu hranu a postupně přidáváme body. Vždy provedeme následující:

Delaunayova vzdálenost se vypočítá, jako

Tento algoritmus má složitost $O(n^2)$.

Další možností je postupné dělení trojúhelníka. Vytvoříme obrovský trojúhelník, který obsahuje všechny body a postupně ho dělíme na menší trojúhelníky. Vždy vybereme jeden bod a ten do triangulace přidáme. Bod může ležet buď uvnitř trojúhelníku nebo na jeho hraně. Pokud leží uvnitř, vznikají z daného trojúhelníku tři nové trojúhelníky. Pokud leží na hraně, vznikají čtyři nové trojúhelníky. Po vytvoření nových hran musíme všechny hrany rekurzivně zlegalizovat (tedy každou hranu a pokud je potřeba i všechny její sousedy).

Pro konvexní mnohoúhelník můžeme triangulaci provést jednoduše. Stačí vybrat jeden bod a spojit ho s každým dalším bodem.

Monotónní mnohoúhelník je takový mnohoúhelník, který v dané ose (např. Y) má pouze jeden extrém (maximální nebo minimální hodnotu). Pro triangulaci takového mnohoúhelníka postupujeme následovně:

Obecný trojúhelník triangulujeme rozdělením tohoto mnohoúhelníka na mnohoúhelníky monotónní a následnou triangulací těchto jeho částí pomocí algoritmu pro triangulaci monotónního trojúhelníka.

Vrcholy v libovolném mnohoúhelníku se dělí na 5 typů:

Abychom získali monotónní mnohoúhelník, potřebujeme se zbavit vrcholů typu Merge a Split. Pro to použijeme sweep line algoritmus (Po Y směrem dolů).

Pro každou hranu, kterou právě protíná sweepline máme uložený tzv. helper vrchol. Jedná se o nejnižší merge vrchol vpravo od jeho hrany takový, že horizontální spojnice mezi hranou a tímto bodem leží celá uvnitř mnohoúhelníka. Tyto helpery spolu s hranami si držíme vy binárním vyhledávacím stromě.

Vrcholy typu split odstraňujeme v okamžiku. kdy jimi prochází zametací přímka. V tomto případě spojíme tento vrchol s pomocníkem zleva nejbližší strany mnohoúhelníka (najdeme pomocí binárního stromu).

Odstranění vrcholů typu merge je složitější. Tyto vrcholy neodstraníme, když jimi zametací přímka prochází, neboť v tomto okamžiku neznáme „situaci“ pod zametací přímkou a nemůžeme vrchol spojovat s vrcholy pod ním. K odstranění merge vrcholů dochází zpětně. V každém z procházených vrcholů testujeme, zda pomocník jeho nejbližších stran je typu merge. Pokud ano, spojíme s ním daný vrchol.

Po dokončení tohoto algoritmu bychom měli mít samé monotónní trojúhelníky, které dokážeme "dotriangulovat".

k-D strom střídavě dělí prostor (2D nebo 3D) na dvě poloviny podle střídajících se os. Ve uzlech jsou uloženy (typicky) dělící čáry a v listech samotné body.

Složitost postavení k-D stromu je $O(n\log n)$.

Vyhledávání v k-D stromě je maličko zajímavější. Rekurzivně sestupujeme stromem a

Složitost vyhledávání v k-D stromě je $O(n^{1-\frac{1}{d}}+k)$, kde $d$ je dimenze a $k$ je počet prvků v dané oblasti.

Tyto jsou značně méně probírány, proto jen obecně myšlenka:

Vytvoříme binární vyhledávácí strom $T$ pro vrcholy podle souřadnice X. Pro každý vrchol $v$ vytvoříme asociovaný vyhledávací strom $T_{ass}(v)$ obsahující pouze vrcholy z podstromnu tohoto bodu $T(v)$. $T_{ass}$ je binární vyhledávací strom podle souřadnice Y.

Při vyhledávání v tomto stromě nejprve vyhledáme podle jedné souřadnice a pak pro všechny vhodné podstromy provedeme vyhledávání podle souřadnice druhé.

Range trees jsou paměťově náročnější, zato jsou rychlejší.