Zde najdete veškeré informace pro cvičení předmětu Algoritmizace geometrických úloh.
Zdroje
V knize Computational Geometry naleznete mnoho algoritmů, které budeme probírat (pro stažení musíte být v sítí školy, připojeni přes VPN a nebo přihlášeni přes bránu E-zdroje).
Cvičení 1
Na cvičení si vysvětlíme problém lokalizace bodu v obecném polygonu bez děr a v konvexním polygonu. Probereme možná řešení a jejich složitosti.
Algoritmus zametání roviny:
- hledání průsecíků úseček
Základní text ke cvičení je k nalezení zde.
Cvičení 2
Motivace pro využití planární mapy, představení datové struktury.
Důkaz složitosti algoritmů pomocí transformace mezi úlohami:
- konvexní obal
Algoritmus zametání roviny:
- aplikace algoritmu pro šrafování
Důkaz řádové složitosti ϑ (bylo na přednášce).
Cvičení 3
Důkaz složitosti algoritmů pomocí transformace mezi úlohami:
- Voronoiův diagram
Planární mapa:
- postup vytváření planární mapy
- vybrané operace nad planární mapou a jejich realizace
Cvičení 4
- důkaz složitosti algoritmu divide and conquer (rozděl a panuj)
- hledání konvexního obalu:
- Jarvisův algoritmus
- metodou divide and conquer
Cvičení 5
- hledání nejbližší dvojice:
- metodou rozděl a panuj
- v 1D a 2D
- intervalový strom
Cvičení 6
- prohledávání intervalu:
- stromem s delením dle osy x a y
- teorémy k Voronoiovu diagramu
Cvičení 7
- průsečík dvou konvexních polygonů
- triangulace:
- algoritmus triangulace
- odstanění ilegální hrany
- počet trojúhelníků a hran v triangulaci
Cvičení 8
- animace výpočtu Voronoiova diagramu pomocí zametání roviny
- rozdělení nemonotónního polygonu na monotónní části
Stručný popis algoritmu rozdělení nemonotónního polygonu na monotónní části.
Cvičení 9
- BSP stromy, viditelnost pomocí BSP stromu
- portal engines
- techniky urychlení W3D
Prezentace id Tech 5 Engine. Prezentace další generace Unreal Engine.
Cvičení 10
- QuadTree a Octree, využití těchto stromů
- variace na stromy typu QuadTree
- využití těchto datových struktur v aplikacích
Prezentace virtuálních textur.
Cvičení 11
- algoritmy pro Level of Detail (LOD)
- problémy vznikající při generování triangulace povrchů (t-juctions, cracks)
Cvičení 12
- opakování probraného učiva