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

**BeRo** · 07-10-2014, 08:21 AM

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:

Code:

// 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;

Code:

// 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;

Code:

// 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;

Code:

// 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:

Code:

     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.

**JC_** · 07-10-2014, 10:01 PM

thank you, it can be usefull for my projects

**paul_nicholls** · 08-10-2014, 12:22 AM

BeRo does it again

Nice dude

**laggyluk** · 08-10-2014, 08:35 AM

umm.. and what's the use for it?

**SilverWarior** · 08-10-2014, 10:45 AM

Triangualtion is used in programaticaly creating 2D polygons made from triangles when all you have is just basic imput data like a shape outline of the specific polygon.
It is also commonly used in image vectoriaztion (converting raster image into verctor based image).

**BeRo** · 08-10-2014, 11:19 AM

Originally Posted by SilverWarior

Triangualtion is used in programaticaly creating 2D polygons made from triangles when all you have is just basic imput data like a shape outline of the specific polygon.
It is also commonly used in image vectoriaztion (converting raster image into verctor based image).

The common image vectorization algorithms are working without triangulation, like my unreleased but for-usage-ready image vectorization algorithm, which I've implemented some years ago. They (at least my algorithm) are working per color image quantization and then greedy from the outside inwards colorwise image contour path tracing together with incremental color plane flipping toward into the inner contour paths.