Algoritmy počítačové kartografie - MZ370G02

• Anglický název: Algorithms of Computer Cartography
• Český název: Algoritmy počítačové kartografie
• Zajišťuje: Katedra aplikované geoinformatiky a kartografie (31-370)
• Fakulta: Přírodovědecká fakulta
• Platnost: od 2024
• Semestr: letní
• E-Kredity: 6
• Způsob provedení zkoušky: letní s.:
• Rozsah, examinace: letní s.:2/3, 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
• Vysvětlení: Od nové akreditace nahrazuje MZ370P13.
• Poznámka: povolen pro zápis po webu; při zápisu přednost, je-li ve stud. plánu
• Garant: doc. Ing. Tomáš Bayer, Ph.D.
• Vyučující: doc. Ing. Tomáš Bayer, Ph.D.
• Neslučitelnost : MZ370P13

Anotace

Anotace předmětu:

Předmět se zaměřuje na automatizaci vybraných kartografických/geoinformatických úloh, popisuje geometrický,
matematický a informatický základ operací prováděných v GIS z pohledu výpočetní geometrie.

Úvod do výpočetní geometrie/ digitální kartografie. Základní algoritmické strategie. Point location problem. Konvexní obálky v 2D a jejich využití. 2D Delauany triangulace, datově závislé triangulace. DMT a jejich analýzy (expozice, sklon). 2D Voronoi diagram. Topologická kostra a její aplikace. Alpha shapes. Booleovské operace s polygony: průnik, sjednocení, rozdíl. Minkowského suma, offset polygonu. Kartografické generalizační algoritmy.

Poslední úprava: Bayer Tomáš, doc. Ing., Ph.D. (13.02.2022)

Literatura

Přehled literatury:

[1] de Berg, van Kreveld, Overmars M., Schwarzkopf O.: Computational Geometry, 2000, Springer

[2] Rourke O. J.: Computational Geometry in C, 2005, Cambridge University Press

[3] Bayer T.: Algoritmy v digitální kartografii, 2008, UK v Praze

[4] Žára J. & kol.: Moderní počítačová grafika, 2004, Computer Press

Poslední úprava: Bayer Tomáš, doc. Ing., Ph.D. (13.02.2022)

Požadavky ke zkoušce

Podmínky zápočtu:

Včasné odevzdání úloh (do zápočtového týdne).

Účast na cvičeních (1 absence povolena).

Zkouška:

Známka závislá na dosaženém bodovém ohodnocení všech odevzdaných úloh.

Hodnocení	Počet bodů (4 úlohy)
1	140
2	130
3	120
4	<120

Poslední úprava: Bayer Tomáš, doc. Ing., Ph.D. (13.02.2022)

Sylabus

Sylabus předmětu:

1. Základní strategie používané ve výpočetní geometrii
- Hrubá síla. Inkrementální konstrukce. Heuristika. Rozděl a panuj. Randomizované algoritmy.

2.Point Location proble
- Poloha bodu a polygonu (Ray Crossing/Winding Number).

3. Konvexní obálky
- Graham, Jarvis scan, inkrementální konstrukce, rozděl a panuj. Využití při kartografické generalizaci, detekce hlavních směrů budov.

4. 2D triangulace, DMT
- Greedy, Delaunay triangulace. DMT. Lineární interpolace vrstevnic. Analýza sklonu a expozice, barevná hypsometrie.

5. Voronoi diagram
- Dualita vzhledem k Delaunay triangulaci. Metody konstrukce. Metoda přirozeného souseda. Nejčastější úlohy v kartografii/geoinformatice řešené s využitím VD.

6. Topologická kostra
- Medial, chordal, linear axis, straight skeleton a jejich použití v kartografii.

7. Alpha shapes
- Alpha shapes a jejich použití v kartografii.

8. Množinové operace s polygony
- Průnik, sjednocení, rozdíl uzavřených oblastí. Offset polygonu (buffer) a jeho konstrukce.

9. Kartografické generalizační algoritmy
- Nejčastěji používané generalizační operátory v digitální kartografii. Generalizace bodových, liniových a plošných znaků.

Poslední úprava: Bayer Tomáš, doc. Ing., Ph.D. (13.02.2022)

Vstupní požadavky

Přehled vstupních požadavků:

• Vybrané pasáže matematiky (lineární algebra ve 2D/3D).
• Pokročilá znalost programovacího jazyka Python (objektově orientované programování).
• Nástroje pro verzování kódu (git).
• Schopnost tvorby rozsáhlejších SW výstupů.
• Logické a abstraktní myšlení.

Poslední úprava: Bayer Tomáš, doc. Ing., Ph.D. (13.02.2022)