Výpočetní geometrie

• 26 hod. přednášky
• 26 hod. projekty

• Student se seznámí s problematikou výpočetní geometrie a jejími typickými problémy.
• Student získá přehled o existujících algoritmech a jejich aplikacích v grafice a poč. vidění.
• Student prohloubí své znalosti matematiky a seznámí se užitečnými vlastnostmi geometrické algebry včetně reálných aplikací.
• Student se zaměří na zvolenou oblast výpočetní geometrie a v rámci projektu vytvoří praktickou aplikaci, projektovou dokumentaci a projekt obhájí.

• Student se naučí odborné terminologii v anglickém jazyce.
• Student se naučí vyhledávat informace v angličtině.
• Student se naučí vytvářet projekty v malém týmu a prezentovat i obhájit výsledky projektu.
• Studenti se zdokonalí v praktickém užívání programátorských nástrojů.

Seznámit se s typickými problémy výpočetní geometrie, získat přehled o existujících řešeních a algoritmech. Prohloubit znalosti matematiky aplikované v počítačové grafice a seznámit se s geometrickou algebrou. Zaměřit studenta na praktické využití výpočetní geometrie a geometrické algebry v grafice a počítačovém vidění. Procvičit tvorbu projektové dokumentace a obhajobu projektu.

• Znalost základů lineární algebry a geometrie (v rozsahu bakalářského studia FIT).
• Znalost základních algoritmů a datových struktur (v rozsahu bakalářského studia FIT).
• Znalost základů počítačové grafiky (v rozsahu bakalářského studia FIT).
• Znalost jazyka C++ a objektově orientovaného návrhu aplikací.

• Csaba D. Toth, Joseph O'Rourke, Jacob E. Goodman: Handbook of Discrete and Computational Geometry, 3rd Edition, 2017.
• Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications, 3rd. ed., Springer-Verlag, 2008.
• Leo Dorst, Daniel Fontijne, Stephen Mann: Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry, rev. ed., Morgan Kaufmann, 2007.

• Leo Dorst, Daniel Fontijne, Stephen Mann: Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry, rev. ed., Morgan Kaufmann, 2007.
• Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications, 3rd. ed., Springer-Verlag, 2008.

1. Úvod do výpočetní geometrie: příklady řešených problému, typické metody, složitost a robustnost algoritmů, numerická přesnost a stabilita.
2. Přehled pojmů z lineární algebry a geometrie, souřadné systémy, homog. souřadnice, afinní a projektivní geometrie.
3. Obecný princip duality, dualita v geometrických úlohách a aplikace.
4. Základy a použití geometrické algebry.
5. Geometrická algebra a konformní geometrie. Geometrické transformace geom. elementů v E2 a E3 s geometrickou algebrou.
6. Praktické využití geometrické algebry a konformní geometrie v počítačové grafice.
7. Testování polohy bodu v polygonu, triangulace polygonu, konvexní obálka ve 2D a 3D, praktické aplikace.
8. Efektivní alg. výpočtu průsečíků (line-triangle intersection, apod.).
9. Hledání intervalů a metody dělení prostoru: range searching a range tree; quad tree, k-d tree, BSP tree.
10. Problém nejbližších (proximity): closest pair; nearest neighbour; Voroniovy diagramy.
11. Triangulace ve 2D a 3D, Delaunay triangulace, tetrahedral meshing.
12. Rekonstrukce povrchu z mračna bodů a z volumetrických dat. Algoritmy pro surface simplification, smoothing a surface remeshing.
13. Další příklady typických úloh výpočetní geometrie a aktuální trendy. Využití lineárního programování: definice a aplikace; half-plane intersection.

Hodnocení studia je založeno na bodovacím systému. Pro úspěšné absolvování předmětu je nutno dosáhnout 50 bodů.

Kontrolovaná výuka zahrnuje půlsemestrální test, individuální projekt a písemnou zkoušku.