I'm looking for a fast and efficient method for covering a 2D (sometimes concave) shape with a fairly regular triangular mesh. I know that the problem of triangulation of a simple (non-intersecting, no holes) polygon has been addressed before (with varied degrees of complexity) e.g. ear-clipping, Seidel's algorithm or Delaunay, but these approaches result in vastly different size triangles and are not all applicable to concave shapes. I am hoping that there could be a more simple solution for the restricted shapes I am particularly interested rather than considering a generic polygon.

The shapes I need to tessellate with triangles are the result of a rectangle clipping a "lune" (think cresent or gibeous moon shapes). Something like these:
[attachment=1602:examplepolys.jpg]
These are mostly either a kind of rounded rectangle (with corners concave or convex), or triangle with a curved (convex or concave) side, although the entire lune could need to be covered with a mesh. Approximating the curves with line segments, is there some kind of appoach with strips of triangles I can take?

Any suggestions?

You may look here and check out Dave's article and code snippet about ear-clipping (supports holes and nesting as well). Or look at Seidel's trapezoid approach, e.g. described here.

Thanks for such speedy replies.

As far as I know, ear clipping works with any kind of 2D shapes. And it definitely works with the shapes you have.[/quote] Yes ear clipping will divide my polygons into triangles, but not similarly sized triangles. Just as ear clipping applied to a rectangle would not generate a nice triangluar mesh (just two triangles), it does not regularly triangulate a near rounded rectangle. Similarly with Seidel's algorithm.

Perhaps I am missing something, or not explaining myself clearly?
If I apply Seidel's algorithm to one of my clipped gibbeous lunes I get a triangulation like this
[attachment=1603:clippedlune02.jpg]
Whereas for a regular mesh what I need to do is cover this region with lots of mostly the same small triangle, with variations to allow for the line segments approximating the curved edges. What I have in mind is to split the shape into trapeziums and fill each with a strip of regular triangles, but I can't quite get my head around it.
End result wanted something like this

[attachment=1604:clippedlune03.jpg]

Perhaps this way: Think of an infinite mesh (build from the regular triangles) that is cut by a polyline. Insert new vertices wherever a polyline segment crosses a mesh edge. Make a new face from the original triangle and the polyline segments inside. Then you'll get a couple of inner ready-to-use triangles, and some small polygons at the inside of the polyline. The latter can be converted using one of the aforementioned algorithms.

In this book, http://www.amazon.co...99760230&sr=8-2, there is an article about subdividing both uniform and non uniform surfaces. The authors website is at http://www.geometrictools.com/ which may help.