Project: Polygon Triangulation

Design the interface between data structures that represent simple polygons and generic algorithms that triangulate simple polygons.

The Standard Template Library (STL) [Austern98, SGI-STL] contains several examples of a similar interface design: Iterators are the interface between sequences of items in container classes and generic algorithms on sequences. However, they (usually) do not modify the container. Among the container classes some modifying functions, e.g., insert or remove, describe a standardized interface for modifying the container classes and can be used for generic algorithms on container classes. This project is expected to design a generic interface in the same spirit for triangulating polygons.

We start with a set of data structures that can represent a simple polygon, and with a set of algorithms that can triangulate it. We suggest to use the Computational Geometry Algorithms Library (CGAL) <www.cgal.org> [Fabri99] as a source of data structures and algorithms in geometry and also as a platform for realizing this project. Possible data structures could be:

• A std::list of 2D points.
• The class CGAL::Polygon_2.
• An individual facet of a 3D polyhedral surface, e.g., the class CGAL::Polyhedron_3.
• While working with the triangulation data structure underlying the class CGAL::Triangulation_2 one can end up in the situation to triangulate a polygonal hole in the triangulation structure.

All these representations would be for simple polygons without holes. An optional extension would be to extend this project to polygons with holes as they can be represented with:

• A std::list of std::list's of 2D points, where the first list is the outer boundary of the polygon and all succeeding lists are the inner boundaries of holes in the polygon, one list per hole.
• The class CGAL::Planar_map_2 can contain faces with holes.
• The class CGAL::Nef_polyhedron_2 can contain faces with holes.

Examples of algorithms that triangulate polygons are:

• Ear-cutting algorithm: An ear is a triangle formed by two consecutive edges of the polygon with a convex angle that contains no other point of a polygon. There exist always at least two ears in a polygon. An ear can be cut from the polygon, reducing its size and thus triangulating it.
• A sweep-line algorithm, see [Chapter 3, deBerg00].
• The constrained triangulation in CGAL. It creates a triangulation of the convex hull of a set of points respecting a set of constrained edges that have to be present in the triangulation, which would be the polygon boundary edges here. Afterwards the triangles in the polygon interior have to be selected, i.e., distinguished from those outside of the polygon.

Clearly iterators can be used in examining the input polygon. The new part will be the modifying part of the algorithms; where do we create and store the result triangles:

• For a single polygon we might just write triangles to an output iterator, for example, for storage in a container or for rendering.
• For polygons embedded in a data structure, such as a triangulation or a polyhedral surface, one wants the result triangles to replace the original polygon and to have the proper neighborhood pointers.

The goal of the project is to design the interface and to realize some of the data structures and algorithms, possibly based on the already existing CGAL implementations. The task includes:

• Analyse the set of operations of each agorithm and how it could be implemented for each data structure considered.
• Find a common set (or several sets) of operations that support the different combinations.
• Implement the interface for the data structures, possibly with adaptors for the existing data structures in CGAL.
• Implement the algorithm based on this interface, maybe also with adaptors to the already existing algorithms in CGAL.
• Test your generic algorithms on the different representations.
• Document the design, for example, in the style of CGAL or using Doxygen.

Prerequisites

This project requires interest in geometry or graphics and some knowledge of geometric algorithms. Since CGAL will be covered later in the course, it might be necessary to learn about CGAL prior to that.

References

[Austern98]

Mathew H. Austern. Generic Programming and the STL: Using and Extending the C++ Standard Template Library. Addison-Wesley, 1998.

[SGI-STL]

Silicon Graphics Computer Systems, Inc. Standard Template Library Programmer's Guide. http://www.sgi.com/tech/stl/.

[Fabri99]

Andreas Fabri, Geert-Jan Giezeman, Lutz Kettner, Stefan Schirra, and Sven Schönherr. On the Design of CGAL, the Computational Geometry Algorithms Library. Software -- Practice and Experience, submitted 1999, to appear. (also available as technical report)

[deBerg00]

Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer, 2nd edition, 2000.