I've updated the BeRoTriangulation.pas now, so the unit contains three 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 these quads from step 4. as far as possible
// 6. Triangulate these quads and construct the final output triangles
// This variant is still experimental, so do use this function variant on your own risk! :-)
// It works for the most all cases, but it outputs more triangles than the both other function variants.
function TriangulateBeRo(const InputPolygons:TBeRoTriangulationPolygons;var OutputTriangles:TBeRoTriangulationTriangles;InputPolygonFillRule:TBeRoTriangulationPolygonFillRule=btpfrEVENODD):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
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;
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
Bookmarks