Triangulate Concave Shape

maze

I am looking for a "good" way to triangulate a closed concave shape of vertices and edges.

"good" is quite a vague term, but the basic principles I'm interested in are:
1) Minimize "sliver" triangles that are very thin and contain really small angles.
2) Must be reasonable to compute. Ideally it would take less than a day to compute the triangulization for a mesh with ~10,000 vertices on a standard computer (so complete brute force is out).

Here is a diagram (initial shape in black):
http://img394.imageshack.us/img394/3077/concavetriangle.png [Broken]

If the mesh was convex, a good strategy would be http://en.wikipedia.org/wiki/Delaunay_trianglulation [Broken] method could work well if I had a fast way of finding the worst possible triangle among a subset of the shape, but I'm having no luck there.

Last edited by a moderator:

mathman

Suggestion (it may not be very good): Form the convex hull of the polygon. Use Delaunay, being careful you don't cross any existing lines. Get rid of lines outside original polygon.

maze

I think the Delaunay triangulization is unique

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving