Aim of the course
The primary objective is to show students the ways to solve basic problems occurring in computational geometry (such as: search for geometric convexity, proximity, intersection, polygonization, and optimization of geometric objects), and present the achievements of computational geometry which are applied e.g. in reality modelling, computer simulations, computer graphics, cartography, and robotics.
Introduction: historical background, the ways of representing geometric objects, geometric data structures, basic methods of solving geometrical problems. Geometric search: the problem of the location of point, the scope of search. Convex envelope. Detection of intersections in 2D and 3D. Polygonization of 2D and 3D objects. Problems of visibility, monitoring problems. The search for the nearest neighborhood. Geometric problems of movement of objects. Informatic problems in computational geometry, usage of computational geometry in modelling, computer simulation, graphics, computer games, etc.
Overview of the course elements
As part of the laboratory classes stuedents learn about the implementation of algorithms of computational geometry with different environments, techniques and languages. Gaining skills in solving basic problems that features computational geometry.
1. Geometria obliczeniowa. Algorytmy i zastosowania, M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf , WNT, 2007
2. Geometria obliczeniowa. Wprowadzenie, F.P. Preparata, M.I. Shamos, Helion, 2003
3. Computational Geometry in C, J. O’Rourke, Cambridge University Press, 2000
4. Geometric Folding Algorithms, E. D. Demaine, J. O’Rourke, Cambridge University Press, 2007
5. Podstawy modelowania krzywych i powierzchni. Zastosowanie w grafice komputerowej, Przemysław Kiciak, WNT 2005