Polygon repair
- Mentors
- sloriot, Andreas Fabri
- Organization
- CGAL Project
- Technologies
- c++
- Topics
- graphics, gis, triangulation, Polygons
Polygons are defined by one outer ring and possibly multiple inner rings representing holes, where each ring is usually represented as a sequence of points. This allows for several undesirable configurations, such as self-intersecting rings, badly nested rings (inner outside outer), and inner rings that split the interior of the polygon into multiple disjoint parts. Such undesirable configurations are considered as invalid polygons in many applications, such as in Geographic Information Systems through ISO 19107.
The aim of this project is to incorporate the polygon repair method originally described in https://doi.org/10.1016/j.cageo.2014.01.009 (but later improved) as a CGAL package. This method consists of three steps: (1) a constrained triangulation of the polygon, (2) labelling of its faces as interior/exterior, (3) extraction of the resulting polygon(s) from the sets of labelled triangular faces.
The method is already implemented using CGAL and freely available as prepair: https://github.com/tudelft3d/prepair. Integrating it with CGAL as a new package would likely involve switching the code's GDAL dependency with new functions for native CGAL types, adding some functionality in the CGAL 2D/3D Triangulations package (proper deletion of constraints), and the writing of CGAL-style templated code (with support for different kernels and so on).