If you have worked with large GIS datasets, I am sure you will agree: ’broken’ polygons are everywhere. Self-touching polygons are often used to represent holes, self-intersecting ones are a common output of generalisation algorithms, and badly nested polygons with holes are interpreted differently in different software.
It might seem like a trivial problem, but it is a more complex than it seems. Whether a polygon is broken or not depends on the polygons themselves, the format they are stored in, your operating system, the libraries you have installed, the software you are using them in, and what you want to do with them.
prepair — pronounced ‘pee-repair’ as in ‘polygon repair’ — solves all possible issues automatically, generating polygons that always conform to the international standards ISO 19107 and OGC Simple Features. It does so quickly, robustly and without moving any points.
prepair works by computing a constrained triangulation of the polygon using CGAL, classifying each triangle as belonging to the interior/exterior, and reconstructing the polygon based on those that were found to be in the interior.
It is available freely under the GPLv3 license (or a commercial license if that is too restrictive for you).
Get it from the prepair repository, or read our paper on the topic:
Ledoux, H., Arroyo Ohori, K., and Meijers, M. (2014). A triangulation-based approach to automatically repair GIS polygons. Computers & Geosciences 66:121–131. [DOI] [PDF]