Algoritmy pro tvorbu digitálních map

Anotace předmětu:

Aplikace algoritmů výpočetní geometrie v digitální kartografií. Geometrické vyhledávání bodů. Konvexní obálky v 2D a jejich vyuužití. 2D Delauany triangulace, datově závislé triangulace. Polyedrické DMT a jejich analýzy (expozice, sklon). 2D Voronoi diagram. Topologická kostra: medial axis, straight skeleton. Kartografické generalizační algoritmy. Booleovské perace s polygony: průnik, sjednocení, rozdíl. Minkowského suma, offset polygonu, konstrukce bufferu.

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

 Přednáška   Téma   Ke stažení  
1, 2  Algoritmy a jejich složitost přednáška
3  Základní pojmy a vztahy výpočetní geometrie přednáška
4  Geometrické vyhledávání bodů přednáška
5  Konvexní obálky přednáška
6, 7, 8 2D triangulace, DMT přednáška
9 Voronoi diagram přednáška
10 Topologická kostra přednáška
11,12 Množinové operace s polygony přednáška
13 Kartografické generalizační algoritmy přednáška

Cvičení:

Implementace vybraných algoritmů v jazyce Java.

 Cvičení   Téma úlohy  Ke stažení 
1. Geometrické vyhledávání bodu zadání
2. Konvexní obálky zadání
3. Digitální model terénu a jeho analýzy zadání
4. Množinové operace s polygony zadání

Součástí každé úlohy odevzdávané za skupinu bude:

  1. technická zpráva se zadáním (v papírové i v elektronické formě),
  2. zdrojový kód aplikace (uložený na FTP serveru),
  3. vstupní/výstupní data (uložená na FTP serveru),
  4. přeložená funkční aplikace (0 errors) pod OS GNU/Linux (popř. Windows) ve formě binárního souboru.
    Budou ošetřeny všechny warningy (0 warnings).

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:

  • zdrojový kód bude naformátován, velikost odsazení 8 znaků TAB (ne SPACE!), oddělování logických částí kódu mezerami,
  • důsledné používání komentářů v kódu: datové položky, metody, třídy, algoritmy.
  • dodržování jazykových konvencí: identifikátory, komentáře ve zdrojovém kódu, názvy souborů, složek, projektů pouze v AJ,
  • 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,
  • důsledné používání komentářů v kódu: proměnné, funkce, třídy, algoritmy a jiné důležité části,
  • vyvarování se nevhodných kostrukcí: příkaz goto, podmínky v negativní formě, číselné hodnoty bez identifikátorů, nevhodné datové typy, platformě závislé konstrukce,
  • GUI aplikace: důsledné používání layoutů, titulek, schopnost maximalizace/minimalizace, user-friendly.

Zdrojový kód aplikací nesplňující tyto požadavky nebude uznán! Žádná z aplikací nesmí využívat dostupné knihovny geometrických algoritmů !!!

Technická zpráva bude obsahovat:

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

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

Pokyny pro odevzdání:

Pokud úloha neobsahuje některý z výše uvedených bodů, její ohodnocení bude 0b. Zadání, vzorce, obrázky nekopírujte z přednášek. Aplikace nesmí využívat jiné knihovny geometrických algoritmů. Elektronická verze technické zprávy ve formátu PDF, u formátu LaTeX odevzdávejte také zdrojový kód. Všechny elektronické dokumenty zazipujte do jednoho archivu.


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 11 5 26
2. 15 21 5 41
3. 20 38 5 63
4. 20  24  5  49
 Celkem  65 94 20 179

Podmínky zápočtu:

  • Včasné odevzdání úloh (do zápočtového týdne)
  • Účast na cvičeních.

Zkouška:

Známka závislá na dosaženém bodovém ohodnocení z úloh. Dosáhne -li student alespoň 90 bodů, absolvuje předmět s níže uvedeným ohodnocením.

 Stupeň   Bodové ohodnocení 
1 110
2 100
3 90
4 <90

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