Zde najdete veškeré informace pro cvičení předmětu Algoritmizace geometrických úloh.

Rozvrh

Středa
10:45 - 12:15, EB113

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