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 zimní 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álka množiny bodů. přednáška
5,6,7 2D/2.5D triangulace, DMT. přednáška
8 Voronoi diagram. přednáška
9 Topologická kostra. přednáška
10 Rekonstrukce povrchů z bodových množin. přednáška
11 Množinové operace s polygony. přednáška
12,13 Kartografické generalizační algoritmy. přednáška

 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) pod OS GNU/Linux (popř. Windows) 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, 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, platformně 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í:

Zadání, vzorce, obrázky nekopírujte z přednášek. Aplikace nesmí využívat externí knihovny (s výjimkou grafických). 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 klasifikace pro akademický rok 2022/2023:

Stav odevzdání úloh (ke dni 1.2.2023):

  • 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 15 10 35
2. 15 20 10 45
3. 20 45 10 75
4. 20  35  10  65
 Celkem  65 103 40 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]

 

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