Delaunay triangulating the 2d polygon with holes

java algorithm geometry delaunay medial-axis
Rogach picture Rogach · Apr 13, 2011 · Viewed 8.6k times · Source

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).

Answer

Kipton Barros picture Kipton Barros · Apr 26, 2011

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.

Related questions

What is the algorithm for finding the center of a circle from three points?

I have three points on the circumference of a circle: pt A = (A.x, A.y); pt B = (B.x, B.y); pt C = (C.x, C.y); How do I calculate the center of the circle? Implementing it in …

Read More
Finding the max/min value in an array of primitives using Java

It's trivial to write a function to determine the min/max value in an array, such as: /** * * @param chars * @return the max value in the array of chars */ private static int maxValue(char[] chars) { int max = chars[0]; for (int ktr = 0; …

Read More
Generating all permutations of a given string

What is an elegant way to find all the permutations of a string. E.g. permutation for ba, would be ba and ab, but what about longer string such as abcdefgh? Is there any Java implementation example?

Read More