BeRoTriangulation - A robust 2D polygon triangulator for simple and complex polygons

[BeRo]

I do want to share my useful BeRoTriangulation unit here. It's a robust 2D polygon triangulator for non-realtime-usages (or with caching on load time) by combining non-constrained delaunay triangulation with the Bowyer–Watson algorithm as first pass with polygon clipping as middle pass and ear clipping as final pass, so it supports even self-intersecting polygon with holes as input and not just only simple polygons.

It needs and uses the Clipper library from http://www.angusj.com/delphi/clipper.php for the polygon clipping work.

And it contains also a second seidel-algorithm-based non-robust variant for realtime-usages.

And here is the link: http://rootserver.rosseaux.net/stuff...angulation.pas

It's licensed under the Boost Software License.

So have a lot fun with it

Edit:

I've updated the BeRoTriangulation.pas again, so the unit contains four different triangulator implementation variants:

// The flexible semi-robust variant by my own scanline-rasterization-like sweeping algoritm. Algorithm steps:
// 1. Add edges from input polygons
// 2. Split intersecting edges
// 3. Split edges at Y coordinates of all polygon points including these of intersection edge intersection points
// 4. Construct y-monotone quads with a trapezoid-style shape with scanline-rasterization-like sweeping from
//    top to bottom and from left to right with the wished polygon fill rule
// 5. Optimize and merge the output from step 4. as far as possible
// This variant is still experimental, so do use this function variant on your own risk! :-)
// It works already pretty good, but it is still in progress.
function TriangulateBeRo(const InputPolygons:TBeRoTriangulationPolygons;var OutputTriangles:TBeRoTriangulationTriangles;InputPolygonFillRule:TBeRoTriangulationPolygonFillRule=btpfrEVENODD;Quality:longint=$7fffffff):boolean;

// Slow bruteforce-style very robust variant with delaunay algorithm, clipping and earclipping for non-realtime usages
// A robust 2D polygon triangulator by combining non-constrained delaunay triangulation as first pass with polygon
// clipping as middle pass and ear clipping as final pass, so it supports even self-intersecting polygon with holes
// as input. It needs and uses the Clipper library from http://www.angusj.com/delphi/clipper.php for the polygon
// clipping work.
// It doesn't support the btpfrABSGEQTWO polygon fill rule, and the output depends on the correctness/accuracy of the
// 3rd-party clipper library
function TriangulateDelaunayClipping(const InputPolygons:TBeRoTriangulationPolygons;var OutputTriangles:TBeRoTriangulationTriangles;InputPolygonFillRule:TBeRoTriangulationPolygonFillRule=btpfrEVENODD):boolean;

// Faster non-robust variant with seidel algorithm for realtime usages
// It supports only the even-odd polygon fill rule in this current implementation, and it can handle only simple polygons (with and without holes)
function TriangulateSeidel(const InputPolygons:TBeRoTriangulationPolygons;var OutputTriangles:TBeRoTriangulationTriangles):boolean;

// Faster non-robust variant with ear clipping algorithm for realtime usages
// It can handle only non-self-intersecting simple polygons without holes
function TriangulateEarClipping(const InputPolygon:TBeRoTriangulationPolygon;var OutputTriangles:TBeRoTriangulationTriangles):boolean;

with the fill rules:

     TBeRoTriangulationPolygonFillRule=(btpfrEVENODD,btpfrNONZERO,btpfrPOSITIVE,btpfrNEGATIVE,btpfrABSGEQTWO);

The TriangulateBeRo variant does support all from gluTess known polygon fill rules: evenodd, nonzero, positive, negative and abs_geq_two

TriangulateBeRo is the best flexible and robust variant, followed by TriangulateDelaunayClipping. But TriangulateDelaunayClipping is depending on the correctness/accuracy of the 3rd-party clipper library. TriangulateSeideland TriangulateEarClipping are faster non-robust triangulation functions for faster usages for example for realtime stuff.