Algoritmy počítačové kartografie

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.