Algorithms in Digital Cartography and GIS

Garant předmětu:

Tomáš Bayer

Lecturer:

Tutor:

Supervisor:

Department of Geomatics

Synopsis:

Automation of digital cartography tasks using rule-based strategies. Implementation of selected cartographic problems in a chosen programming language. Preparation and design of graphical outputs in Qt library.

Requirements:

1. Knowledge of fundamental passages of 2D geometry and discrete mathematics.

2. Programming skills in the chosen language (including OOP).

3. Overview of basic algorithmic strategies (recursion).

4. Knowledge of selected passages of theoretical computer science (graph theory).

5. Practical experience with the implementation of algorithms.

6. Experience with the LaTeX typographic system is welcome.

Syllabus of lectures:

1. Basic concepts and relations of computational geometry.

2. Basic algorithmic strategies in computational geometry.

3. Geometric point search.

4. Convex huls in 2D.

5. Triangulation algorithms in 2D/2.5D.

6. Digital terrain model and its analysis.

7. Voronoi diagram and generalized Voronoi tessellation.

8. Topological skeleton and its application in cartography.

9. Boolean operations with polygons.

10. Buffer.

11. Algorithms for cartographic generalization.

12. Reconstruction of surfaces from dense point sets.

13. Development and tendency of contemporary digital cartography.

Syllabus of tutorials:

Work on problems in teams of two or three students:

1. Point Location Problem and its implementation. Fast location of a point within a set of non-convex polygons.

2. Simplification of building footprints using minimum area enclosing rectangle, wall average, and weighted bisector methods.

3. Construction of digital terrain model by 2D Delaunay triangulation, contour line construction. Analysis of terrain slope and terrain aspect.

4. Partial modification of the generalized feature using minimum energy spline. Testing multiple models with different fixed elements, generalized elements, and obstacles.

Study Objective:

1. Automation of tasks and procedures in digital cartography.

2. Overview of rule-based strategies for solving cartographic problems.

3. Interaction of digital cartography with computer graphics, computational geometry, geoinformatics, and mathematics.

4. Overview of basic algorithmic strategies in cartography/computational geometry.

5. Design of an optimal solution to a cartographic problem.

6. Practical implementation of selected procedures in the programming language.

Study materials:

[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

Note:

Further information:

http://web.natur.cuni.cz/~bayertom/index.php/teaching/algoritmy-v-digitalni-kartografii

No time-table has been prepared for this course

The course is a part of the following study plans:

• Geodézie a kartografie, specializace Geomatika (compulsory elective course)
• Geodézie a kartografie, specializace Geomatika (compulsory elective course)