Algoritmy počítačové kartografie

Anotace předmětu:

Ú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.

Přednášky:

Seznam přednášek pro letní semestr.

 Přednáška   Téma  Ke stažení  
 1
Algoritmické strategie ve výpočetní geometrii.

přednáška
přednáška

 2 Point location problem. přednáška
 3, 4 Konvexní obálky. přednáška
 5, 6, 7 2D triangulace, DMT. přednáška
 8 Voronoi diagram. přednáška
 9 Topologická kostra. přednáška
 10, 11 Kartografické generalizační algoritmy. přednáška
 12 Rekonstrukce objektů z bodových množin. přednáška
 13 Množinové operace s polygony. přednáška

 

Další přednášky:

Komprese a kompresní algoritmy: přednáška, text.

 

Cvičení:

Implementace vybraných algoritmů v jazyce Python. Termín odevzdání je stanoven vyučujícím.

 Cvičení   Téma úlohy Ke stažení 
1. Geometrické vyhledávání bodu. zadání
2. Generalizace budov. zadání
3. Digitální model terénu a jeho analýzy. zadání
4. Energetické spliny. zadání  návod


Pro odevzdávání úloh používejte github. Součástí každé úlohy odevzdávané za skupinu bude:

  1. technická zpráva se zadáním,
  2. zdrojový kód aplikace,
  3. vstupní/výstupní data,
  4. přeložená funkční aplikace (0 errors) ve formě binárního souboru.

Za nefunkční bude aplikace považována, pokud:

  • při zpracování dat dojde k pádu (runtime chyby, ...),
  • dává špatné výsledky,
  • nevrací systémové prostředky (memory leaks, ...).

Požadavky na zdrojový kód aplikace:

  1. zdrojový kód bude naformátován, oddělování logických částí kódu mezerami,
  2. důsledné používání komentářů v kódu: datové položky, metody, třídy, algoritmy a jiné důležité části.
  3. dodržování jazykových konvencí: identifikátory, komentáře ve zdrojovém kódu, názvy souborů, složek, projektů pouze v AJ,
  4. dodržování typografických zásad:
  • identifikátory konstant verzálkami,
  • identifikátory proměnných minuskulemi, víceslovné se spojovníkem _,
  • identifikátory metod minuskulemi, víceslovné bez spojovníku, počáteční písmena verzálkami,
  1. vyvarování se nevhodných kostrukcí: příkaz goto, podmínky v negativní formě, číselné hodnoty bez identifikátorů, nevhodné datové typy, platformně závislé konstrukce,
  2. GUI aplikace: důsledné používání layoutů, titulek, schopnost maximalizace/minimalizace, user-friendly.
  3. zdrojový kód nesmí využívat externí knihovny geometrických algoritmů.

Zdrojový kód aplikací nesplňující tyto požadavky nebude uznán!

Textová část úlohy bude obsahovat:

  1. Zadání.
  2. Údaje o bonusových úlohách + počet bodů.
  3. Popis a rozbor problému + vzorce.
  4. Popisy algoritmů formálnímm jazykem.
  5. Problematické situace a jejich rozbor (tj. simplexy) + ošetření těchto situací v kódu.
  6. Vstupní data, formát vstupních dat, popis.
  7. Výstupní data, formát výstupních da, popis.
  8. Printscreen vytvořené aplikace.
  9. Dokumentaci: popis tříd, datových položek a jednotlivých metod..
  10. Závěr, možné či neřešené problémy, náměty na vylepšení.
  11. Seznam literatury.

Text vytvořen v systému LaTeX: bonifikace +5b.

Návod, jak psát dokumentaci k programu (technickou zprávu): http://ksvi.mff.cuni.cz/~kryl/dokumentace.htm

Pokyny pro odevzdání:

Zadání, vzorce, obrázky nekopírujte z přednášek.
Aplikace nesmí využívat externí knihovny (s výjimkou grafických a importních).
Elektronická verze technické zprávy ve formátu PDF, u formátu LaTeX odevzdávejte také zdrojový kód.
Všechny elektronické dokumenty odevzdat přes github.

Stav klasifikace pro akademický rok 2022/2023:

Stav odevzdání úloh:

  • Detaily odevzdaných úloh [zde].
  • Přehled jednotlivých úloh [zde].

Informace jsou průběžně aktualizovány...


Bodové hodnocení úloh:

Každá z úloh obsahuje povinnou část (musí být vyřešena) a volitelnou část (může být vyřešena). Povinná část úlohy je hodnocena fixním počtem bodů, volitelná část v závislosti na zvolených problémech. Celkové hodnocení úlohy je součtem ohodnocení povinné části, volitelné části, a zpracování technické zprávy.

Úloha  Povinná část   Volitelná část   Protokol   Max 
1. 10 25 10 (+5) 35
2. 15 20 10 (+5) 45
3. 20 45 10 (+5) 75
4. 20  35 10 (+5)  65
 Celkem  65 125 40 (+20) 220

 

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ů (3/4 úlohy)
1 120/140
2 110/130
3 100/120
4 <100/120

 

Literatura:

[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

Užitečné odkazy:

  • Velmi zajímavá prezentace zabývající se zásadami návrhu grafického rozhraní. [download]
  • Dvě prezentace zaměřené na QT. [download], [download]