Menu
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).
268
The Delaunay triangulation is a triangulation which is equivalent to the nerve of the cells in a Voronoi diagram, i.e., that triangulation of the convex hull of the points in the diagram in which every circumcircle of a triangle is an empty circle (Okabe et al. 1992, p. 94).
Computing the triangulation of a polygon is a fundamental algorithm in computational geometry. In computer graphics, polygon triangulation algorithms are widely used for tessellating curved geometries, as are described by splines [Kumar and Manocha 1994].
Every triangulation of an n-gon has exactly n − 2 triangles. 3. Polygon in picture has n = 13, and 11 triangles.
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.
140
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
