Sylabus
Sylabus předmětu: 1. Základní strategie používané ve výpočetní geometrii - Hrubá síla.
Inkrementální konstrukce. Heuristika.
Rozděl a panuj. Randomizované algoritmy. 2.Point Location proble - Poloha bodu a polygonu (Ray Crossing/Winding Number). 3.
Konvexní obálky - Graham, Jarvis scan, inkrementální konstrukce, rozděl a panuj. Využití při kartografické generalizaci, detekce hlavních směrů budov. 4. 2D triangulace, DMT - Greedy, Delaunay triangulace.
DMT. Lineární interpolace vrstevnic.
Analýza sklonu a expozice, barevná hypsometrie. 5. Voronoi diagram - Dualita vzhledem k Delaunay triangulaci.
Metody konstrukce. Metoda přirozeného souseda.
Nejčastější úlohy v kartografii/geoinformatice řešené s využitím VD. 6. Topologická kostra - Medial, chordal, linear axis, straight skeleton a jejich použití v kartografii. 7.
Alpha shapes - Alpha shapes a jejich použití v kartografii. 8. Množinové operace s polygony - Průnik, sjednocení, rozdíl uzavřených oblastí.
Offset polygonu (buffer) a jeho konstrukce. 9. Kartografické generalizační algoritmy - Nejčastěji používané generalizační operátory v digitální kartografii.
Generalizace bodových, liniových a plošných znaků.
Anotace
Anotace předmětu:
Předmět se zaměřuje na automatizaci vybraných kartografických/geoinformatických úloh, popisuje geometrický, matematický a informatický základ operací prováděných v GIS z pohledu výpočetní geometrie.
Ú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.