Tessellating an arbitrary polygon by tiling triangles

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

As Jason Orendorff pointed out, you should try to use Triangle to generate a quality mesh. It has lots of options that you can play with to try to get an isotropic mesh. Then, you could try to use an iterative algorithm to create a well-centered triangulation. More details are listed on this publications page. I have implemented the 2007 paper "Well-Centered Planar Triangulation -- an Iterative Approach," and it gives decent results on medium sized meshes. A well-centered triangulation is one in which all the circumcenters of triangles lie inside the respective triangle. Since you want something slightly different, you could simply try to change the error metric involved. You could find a measure of "non-congruence" among the triangles and minimize that error. Most likely such an error function will be non-convex, so the non-linear conjugate gradient optimization described is as well as you can do.