Search code examples
javaalgorithmgeometrydelaunaymedial-axis

Delaunay triangulating the 2d polygon with holes

I want to triangulate the complex (but not self-intersecting) polygon with holes, so that resulting triangles all lay inside the polygon, cover that polygon completely, and obey the Delaunay triangle rules.

Obviously, I could just build the Delaunay triangulation for all points, but I fear that some edges of the polygon will not be included into resulting triangulation.

So, is such triangulation possible? And if yes, how can I do it?

Just in case - I need it to construct the approximation of polygon medial axis (I hope it can be done via connecting all circumference points of resulting triangles).

Solution

  • It sounds like you want constrained Delaunay triangulation. The "holes" can be implemented by constraining input edges to remain unbroken in the triangulation.

    See the Triangle and poly2tri projects for implementations.