Algoritmy v digitální kartografii

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.

Přednášky:

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

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

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

2 Geometrické vyhledávání bodů 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 Množinové operace s polygony přednáška
11,12 Kartografické generalizační algoritmy přednáška

 












Cvičení:

Implementace vybraných algoritmů v jazyce C++ pod OS GNU/Linux. 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. 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:

  1. zdrojový kód bude naformátován, velikost odsazení 8 znaků TAB (ne SPACE!), 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.
  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,
  5. důsledné používání komentářů v kódu: proměnné, funkce, třídy, algoritmy a jiné důležité části,
  6. 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,
  7. 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. Údaje o bonusových úlohách.
  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.

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 (lze includovat pouze hlavičkové soubory definované normou). Testování provádějte v režimu Release (ne Debug!). 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.

Stav odevzdání pro akademický rok 2018/2019:

Konečný termín pro odevzdání úloh je neděle, 3. února, 2019. Pokud nebudou do tohoto termínu opraveny chyby v úlohách, výsledné hodnocení bude F.

Stav ke dni 21.1.2019:

  • 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. Každé vrácení úlohy z důvodu chyb ve funkcionalitě aplikace, závažných chyb ve zdrojovém kódu, v protokolu je spojeno s odečtením 1b.

Ú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 (100%)

Zkouška:

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

 Stupeň   Bodové ohodnocení(4Ú)
Bodové ohodnocení(3Ú)
A 110 85
B 105 80
C 100 75
D 95 70
E 90 65
F <90 <65

 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]

Ukázkové aplikace:

Ukázky aplikací vytvořených v prostředí QT Creator. Aplikace jsou opatřeny stručným komentářem.

  • Úvodní aplikace vytvářející tlačítko a label. [download]
  • Práce s komponentami v QT Creatoru. [download]
  • Jednoduchá grafika v prostředí QT Creatoru, kostra aplikace pro RayCrossingAlgorithm. [download].
  • Detekce polohy bodu a úsečky s využitím Half Plane testu v QT Creatoru. Příklad využívá poněkud uměle několik tříd s cílem ilustrovat vzájemnou komunikaci jednotlivých instancí. Varianta využívající vlastní třídu Point [download].