155ADKI Algoritmy digitální kartografie a GIS

Anotace

Předmět je zaměřen na vybrané pasáže výpočetní geometrie a počítačové kartografie. Zahrnuje popis a implementaci vybraných metod a nástrojů digitální kartografie s důrazem na automatizované zpracování kartografických dat.

Předmět je vhodný i pro studenty doktorského studia, kteří by se chtěli věnovat návrhu a vývoji nových metod automatizovaného zpracování kartografických dat.

Vstupní požadavky

Znalost programovacích jazyků C++/Python vybraných pasáží lineární algebry a geometrie.

Doporučená literatura

• de Berg, van Kreveld, Overmars M., Schwarzkopf O.: Computational Geometry, 2000, Springer
• Rourke O. J.: Computational Geometry in C, 2005, Cambridge University Press
• Bayer T.: Algoritmy v digitální kartografii, 2008, UK v Praze
• Žára J. & kol.: Moderní počítačová grafika, 2004, Computer Press

Podmínky ukončení předmětu

Zápočet

• Včasné odevzdání úloh dle harmonogramu.
• Účast na cvičeních.

Zkouška

• Dle dosaženého bodového hodnocení za odevzdané úlohy (bude upřesněno na cvičení).

Harmonogram pro akademický rok 2023/2024

Harmonogram přednášek

Vyučující: doc. Ing. Tomáš Bayer, Ph.D.

Datum	Téma přednášky	Přednáší
26.9.	Algoritmické strategie ve výpočetní geometrii (PDF)	TB
3.10.	Point location problem. (PDF)	TB
10.-17.10.	Konvexní obálka množiny bodů (PDF)	TB
24.10-7.11.	2D/2.5D triangulace, DMT.	TB
24.10.-31.10	Analýza, klasifikace a extrakce objektů z bodových mračen	TB
7.11.	Voronoi diagram.	TB
14.11.	Topologická kostra. (PDF)	TB
21.11.	Rekonstrukce povrchů z bodových množin. (PDF)	TB
28.11.	Množinové operace s polygony. (PDF)	TB
5.-12.12.	Kartografické generalizační algoritmy.	TB

Cvičení

Řešení úloh ve zvoleném skriptovacím jazyce (C++/Python). Odevzdávání a hodnocení po skupinách.

Každá z úloh obsahuje povinnou část a volitelnou část. Povinná část úlohy je hodnocena fixním počtem bodů, volitelná část v závislosti na zvolených a vyřešených problémech.

Celkové hodnocení úlohy je součtem ohodnocení povinné části, volitelné části, a zpracování technické zprávy.

Datum	Téma úlohy	Cvičí
3.10.	JPEG komprese rastru. (PDF)	TB
17.10.	Clusterizační algoritmy	MP
21.11.	Nejkratší cesta grafem (PDF)	TB
5.12.	Metoda hlavních komponent	MP

Každá úloha bude obsahovat:

1. Zadání.
2. Údaje o bonusových úlohách.
3. Popis a rozbor problému + vzorce.
4. Popisy metod/algoritmů formálním jazykem.
5. Vstupní data, formát vstupních dat, popis.
6. Výstupní data, formát výstupních dat, popis.
7. Závěr, možné či neřešené problémy, náměty na vylepšení.
8. Seznam literatury.