PředmětyPředměty(verze: 945)
Předmět, akademický rok 2023/2024
   Přihlásit přes CAS
Aplikovaná výpočetní geometrie - NPGR016
Anglický název: Applied Computational Geometry
Zajišťuje: Katedra softwaru a výuky informatiky (32-KSVI)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2019
Semestr: letní
E-Kredity: 5
Rozsah, examinace: letní s.:2/1, Z+Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Způsob výuky: prezenční
Další informace: http://afrodita.zcu.cz/~kolinger/vyukaUK.html
Poznámka: povolen pro zápis po webu
Garant: prof. Dr. Ing. Ivana Kolingerová
Třída: DS, softwarové systémy
Informatika Bc.
Informatika Mgr. - volitelný
Kategorizace předmětu: Informatika > Počítačová grafika a geometrie
Anotace -
Poslední úprava: T_KSVI (22.05.2003)
Předmět se zabývá postupy a datovými strukturami z oblasti algoritmické výpočetní geometrie využitelnými pro řešení geometricky formulovaných úloh především z oblasti počítačové grafiky a jejích aplikací, dále např. rozpoznávání, databázových systémů, umělé inteligence, statistiky i jiných oblastí. Příklady řešených problémů jsou geometrické vyhledávání, triangulace, vzájemná poloha geometrických objektů. Příklady užitých metod jsou zametání, dualita, rozděl a panuj, Voronoiovy (Voroného) diagramy. Cvičení: rozbor algoritmů a návrh nových a prezentace studentských prací.
Podmínky zakončení předmětu -
Poslední úprava: prof. Dr. Ing. Ivana Kolingerová (21.06.2018)

Podmínky jsou uvedeny na http://afrodita.zcu.cz/~kolinger/AVG/AVG_c.htm.

Literatura -
Poslední úprava: prof. Dr. Ing. Ivana Kolingerová (21.06.2018)

1. O' Rourke, Joseph: Computational Geometry in C, Cambridge University Press, 1.vydání, 1994 nebo 2.vydání, 2000

2. de Berg, Mark, van Kreveld, Marc, Overmars, Mark, Schwarzkopf, Otfried: Computational Geometry, Algorithms and Applications, Springer Verlag, 1.vydání, 1997 nebo 2.vydání, 2001

3. Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction, Springer-Verlag, New York Berlin Heidelberg Tokyo, 1985

4. Podklady přednášek v PowerPoint poskytnuté vyučujícím a další materiály distribuované na cvičení

Doporučuje se znalost angličtiny na úrovni dovolující studovat anglické prameny.

Sylabus -
Poslední úprava: prof. Dr. Ing. Ivana Kolingerová (20.06.2018)

1. Výpočetní geometrie jako nástroj pro geometrické a grafické aplikace

2. Geometrické vyhledávání - lokace bodu, hledání intervalů

3. Konvexní obálky v 2D a 3D

4. Voroného diagramy v 2D a 3D - vlastnosti, konstrukce

5. Aplikace a zobecnění Voroného diagrammů

6. Rovinné triangulace (Delaunayova, greedy, datově závislá, s omezením, s minimální váhou, multikriteriálně optimalizovaná) a jejich aplikace

7. Tetrahedronizace a jejich aplikace

8. Triangulace polygonu, dělení polygonu na konvexní části, na lichoběžníky, teorém obrazové galerie

9. Střední osa

10. Rekonstrukce povrchu z rozptýlených bodů

11. Průsečíky a průniky (úsečky, polygony, poloroviny, dualita)

12. Podle času a zájmu doplňková témata: psaní odborných článků, prezentace, kreativita

 
Univerzita Karlova | Informační systém UK