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.

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.

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,

5. 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,
6. GUI aplikace: důsledné používání layoutů, titulek, schopnost maximalizace/minimalizace, user-friendly.
7. 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.

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.

Literatura:

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]