Tessellating an arbitrary polygon by tiling triangles

Question

I need to fill an arbitrary polygon using a near-uniform tiling of triangles. How would I do this? You may provide either references to existing algorithms or even simply ideas or hints of your own.

The following is presumed:

• The polygon may be convex (but bonus points if you come up with an algorithm that works for concave shapes)
• The polygon has an arbitrary number of edges (3 or more)
• The amount of tessellation (preferably the number of vertices added by the algorithm) should be parametrized
• The polygon's edges may be divided by the algorithm
• Triangles should be nearly uniform in size and shape (i.e. corners will tend towards 60 degrees)
• Preferably the number edges at a vertex should be few rather than many. This will likely follow from the previous point (I.e. the algorithm should produce a "clean mesh").

This is not an easy problem to solve and I expect that a "heuristic" solution may be the most efficient... (right?)

Answer 1

Does Triangle do what you want?

(The explanations of the algorithms on that site are better than whatever I could come up with.)