Tessellating an arbitrary polygon by tiling triangles

Does Triangle do what you want?

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

Doesn't actually sound that complicated, algorithmically. Or am I missing anything?

Some pseudocode:

• Place an axis-aligned enclosing square tightly around your polygon.
• Subdivide each square into four children (quad-tree like), where the number of iterations determines your "amount of tessellation".
• Each resulting square is either cleanly outside your polygon (=ignore), cleanly inside your polygon (=split into two triangles of resulting tesselation along the diagonal) or intersects your polygon.
• Exact cases for the intersection squares are left as an exercise to the reader. ;-) [At this point in time, at least.]

It will give you triangles with 45°/45°/90° angles though. If you want as close to 60° as possible, you should start with tessellating the surface of your polygon with hexagons (with the size of the hexagon being your "amount of tessellation") and then checking each of the six 60°/60°/60° triangles that make up these hexagons. For these triangles you do the same as with the squares in the above pseudocode, except for the fact that you don't need to split the ones that cleanly inside your polygon as they are already triangles themselves.

Is this of any help whatsoever? Should work for any polygon (convex/concave/with holes in them), I think, given that what exactly you do for intersecting squares/triangles handles such polygons.