one developer has done this, and says "It was very easy",
which seems rather surprising!
Valéry Moya wrote in July 2009:
"I wrote my own glu tesselator. Grabbing
the tessellation from the callbacks isn't all that hard and doesn't
require too much code to get working. (In fact, I got it working
with just 2 of the callbacks registered: GLU_TESS_BEGIN and
GLU_TESS_VERTEX.) In my trial, I was able to get tessellations
from lists verts that make up the contour of the polygon I wanted to
tessellate (with no overlapping edged, but allowing holes defined as
counterclockwise list of verts). The "hard" part is that you need
to handle getting the triangulated verts as triangles, triangle fans
and triangle strip order but this not as bad as it sounds to keep
track of. "
Delaunay triangulations, which apparently have desirable traits for some
purposes, but are a bit overkill for the general case. For our
simpler case it can produce "Constrained Delaunay", which means no
Source is free and portable, only one source file (triangle.c) which
makes it easy to integrate with.
One small drawback: You can't just tell it which segments are the
edges of your hole. Instead, you must supply some point that lies
within the hole. Triangle triangulate the hole, then does some
kind of "flood fill" to empty it. It's inefficient, but what's worse is
it requires the caller to compute a point-in-polygon for the hole. This
is a non-trivial algorithm for an arbitrary complex polygon.
In 2008.01, i adapted the Triangle code with a wrapper to call it
from vtlib. It works quite well, for a very large number of
polygons. However, there are some (rare) cases of degenerate
geometry where it will crash. In particular:
It does not like
duplicate vertices or duplicate edges. 'Duplicate' in this case is
relative to numeric precision: For a building 10-100 meters in size, two
vertices within 8cm of each other, defining a very short edge, can cause
Triangle to crash.
It does not like it when a hole (inner ring) in the polygon has
a vertex in the same location as one in the outer ring (crash).
a Free library which contains a cleaned-up version of the Narkhede
implementation of the Seidel algorithm (above)? No. Perhaps
it did back in 2001, but as of 2007, it contains code to call
"Triangle". It is actually useful as good example code
of how to call Triangle.
"Subdivision using monotone polygons and a sweep line algorithm, O(n
log n) time and O(n) storage"
Supports holes, makes a lot of very skinny triangles.
It compares the speed of Poly2Tri vs. some other
triangulation implementations, and it claims to be faster, although the
triangles produced are very skinny slivers.
open source implementation is available at PolygonTriangulator.cxx
(google it), by Thomas Kittelmann, which says it is adapted from
implementation by Wu Liang (2005), which appears to be part of a project
called "Atlas LXR"
Says it is "Based on the paper Sweep-line algorithm for constrained
Delaunay triangulation by V. Domiter and and B. Zalik"
BSD license. Lives on google-code.
I evaluated it on 2011-07-19. It managed to tessellate some
input which Shewchuk's Triangle couldn't not. However, it still
crashed on some input, like the polygon to the right. Notice how,
once again, one of the polygon's holes (inner rings) exactly touches the
outer ring. The algorithm seems to regard this as degenerate (and
does not even detect it to avoid crashing) but it is unfortunately a
commonly encountered shape.