MCS 481: Computational Geometry
University of Illinois at Chicago
Overlapping polygons and a triangulation of the induced planar decomposition.
CGAL and its dependencies are available as binary packages for some operating systems, including several versions of GNU/Linux, and this is often the easiest way to install these programs. For example, on recent versions of Debian GNU/Linux, all of the necessary packages can be installed with the command:
apt-get install g++ libcgal5 libcgal-demo
Your course grade will be determined on the following basis:
- Computational Geometry in general
- Preparata, F. and Shamos, I. Computational Geometry: An Introduction, Springer-Verlag, 1990.
- O'Rourke, J. Computational Geometry in C, Cambridge University Press, 2001.
- This is a good reference for details of implementation in a low-level language like C
- Cormen, T., Leiserson, C., Rivest, R., and Stein, C. Introduction to Algorithms, 2nd ed., MIT Press, 2001.
- This general reference on data structures and algorithms covers some computational geometry in chapter 33
- Convex hulls
- Segment Intersection and Map Overlay
- Demo applet: Plane sweep for segment intersection by Wei Qian
- Select "Data Set 1" then use the horizontal scrollbar to visualize the sweep.
- The DCEL representation of a planar subdivision is discussed in Section 1.2.3 of Preparata and Shamos (see reference above)
- An important special case of the overlay of planar subdivision is the polygon boolean operation problem, i.e. computing the intersection, difference, or union of two polygons. The intersection case is also called polygon clipping.
- Polygon Triangulation and the Art Gallery Problem
- Voronoi diagrams