Mesh - Triangles algorithm

Since you say you have a mesh, which contains both points and connectivity (e.g., polygons on the boundary are defined), I am assuming that you are just looking to tessellate a general polygon into triangles. If I am correct, then there actually is a name for the approach you're talking about. It is called "ear clipping." But, your approach is insufficient. If the polygon is concave then your method will not maintain the correct shape as you clip off triangles, and some of the triangles will be folded, e.g., if the starting polygon is counterclockwise (when viewed from one side), then some of the resulting triangles will be clockwise---facing the other way. To get it to really work properly you have to look at the concave-ness of the ear that you wish to clip off, and never clip a concave ear. Here is a document that talks about generalized ear-clipping:

Triangulation by Ear Clipping

(There is also an implementation at that site. Dave's method won't give you the best quality triangles, but it will give you a triangulation.)

That said, the way you wrote your post, I actually have the feeling that you may not really have a mesh. You may simply have a point cloud. If it is 2D, you can simply do a Delaunay triangulation, which will give you the "best" set of triangles. The boundary will be convex, e.g., it might not retain the shape of the original object you started with. But it will be a good convex representation. If you can break the original object into convex partitions, then generate a separate point cloud for each partition, then triangulate each point cloud and then recombine, then you could use this for concave objects. Or, you could do constrained Delaunay, which isn't easy, but then you have to know the boundary exactly. You also can do something similar for 3D, something called Delaunay Tetrahedralization.

Er, this sounds complex, doesn't it? Well, if your problem is very general, you probably will find that simpler methods are insufficient. If your problem is always constrained, always very simple in some way, then easier methods might work. We can possibly advise on this, but you will have to give more details on the constraints/limits of your problem and input.

Quote:

Original post by grhodes_at_work There is also an implementation at that site. Dave's method won't give you the best quality triangles, but it will give you a triangulation.

You might want to be more precise for the OP and define what "best quality triangles" mean. At first glance, it sounds like the ear clipping algorithm and my implementation are bad :) That algorithm and my implementation do exactly what they are supposed to do: triangulate a polygon by clipping an ear at a time. Perhaps you meant "best quality" to refer to the empty circumcircle constraint for Delaunay triangulation, which translates to having triangles which maximize their minimum internal angles.

Quote:

Original post by Dave Eberly Quote: Original post by grhodes_at_work There is also an implementation at that site. Dave's method won't give you the best quality triangles, but it will give you a triangulation. You might want to be more precise for the OP and define what "best quality triangles" mean. At first glance, it sounds like the ear clipping algorithm and my implementation are bad :) That algorithm and my implementation do exactly what they are supposed to do: triangulate a polygon by clipping an ear at a time. Perhaps you meant "best quality" to refer to the empty circumcircle constraint for Delaunay triangulation, which translates to having triangles which maximize their minimum internal angles.

Dave, you're correct. That is exactly what I meant. I should have been clear about that. And I shouldn't have really focused the comment by pointing at your implementation specifically either. Your description and implementation work just fine, depending on whether or not you care about having triangles that best matach a Delaunay triangulation. Please accept my apology.

Ear-clipping is a good approach, and just in some cases (e.g., polygons that may have lots of colinear vertices) it is a good idea to add a "closest-to-Delaunay-ear" constraint when picking which ear to clip.