Robust, fast complex polygon (with holes) triangulation c/c++ library with permissive license
I am a developer of the open-source game, Bitfighter. As per the following SO post, we have used the excellent 'Triangle' library for mesh-zone generation for use with our in-game AI (robots):
Polygon Triangulation with Holes
However, we ran into a small snag when wanting to package our game for Debian - the use of the 'Triangle' library will make our game be considered as 'non-free'.
We have been extremely pleased with the performance of the 'Triangle' library, and don't really want to give it up; however, we don't like dealing with license issues either. Therefore we have embarked upon a quest to find a suitable, permissively-licensed replacement that can match 'Triangle' in its robustness and speed.
We're looking for a C or C++ library for dividing large, complex, areas into triangles, that can handle any type of irregular polygons placed together in any manner, as well as holes. Robustness is our primary need, with speed almost as important.
I have found poly2tri, but it suffers from a bug in which it cannot handle polygons with coincident edges.
We have found several libraries, but all seem to suffer from one thing or another: either too slow, or don't handle holes, or suffer from some bug. Currently we are testing out polypartition and we have high hopes.
What are the best alternatives to the great 'Triangle' library, but have a permissive license?
Answer
I found a solution. It was poly2tri after all, with the use of the excellent Clipper library, and some minor algorithmic additions to the inputs.
Our process is as follows:
- Run all our holes through Clipper using a union with NonZero winding (this means that inner holes are wound the opposite direction as outer ones). Clipper also guarantees nice clean input points with no repeats within epsilon.
- Filter our holes into ones that are wound counter-clockwise and clockwise. Clockwise holes meant the hole was circuitous and that there was another concentric area inside that needed to be triangulated
- Using poly2tri, triangulate the outer bounds and each clockwise polygon found, using the rest of the holes as inputs to poly2tri if they were found within one of the bounds.
Result: poly2tri seems to triangulate just about as fast as Triangle and has so far been very robust with everything we've thrown at it.
For those interested, here are our code changes.
Update
I have attempted to pull out our clipper-to-poly2tri code, with our robustness additions, into a separate library which I started here: clip2tri