DJ_AM_Juicebox
asked on
Concave polygon to triangles
Hi,
I have a 2d concave polygon, defined as a list of x,y points. I want to decompose it into a set of triangles. Is there some pre-made algorithm already written in java/c/c++ anyone knows of that will do this for me?
Thanks
I have a 2d concave polygon, defined as a list of x,y points. I want to decompose it into a set of triangles. Is there some pre-made algorithm already written in java/c/c++ anyone knows of that will do this for me?
Thanks
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
A Delaunay triangulation of the vertices of a concave polygon can contain triangles that are outside of the polygon.
Is that what you wanted?.
Is that what you wanted?.
Remove that triangle, and replace the two edges with a new edge joining the end points to form a new polygon.
repeat until you are down one triangle