Triangulation Techniques

I can think of one simple algorithm. To start off your algorithm, pick three points and make a triangle from them. Now add all the other points one by one. If the point is already in one of the triangles, substitute the containing triangle by three triangles formed by the sides of the old triangle and the new point; If the point is outside, add triangles for all the sides of the convex hull of the existing triangles.

If you are OK with having O(n^2) performance, this shouldn't be too hard to write. Of course, you should also consider using an external library (CGAL, QHull, Poly2Tri...).

If your points are ordered, e.g., in a row-column format for example, then you can directly compute the triangulation based on the known order. This can be, basically, the fastest you could hope for.

For general triangulation, frankly, Delaunay triangulation is a brute force approach. That is, it treats an arbitrary set of points without any special knowledge or optimization based on a specific use case.

Within the rules that define a Delaunay triangulation, there is an incremental approach that starts with a big super triangle that covers the entire batch of points (a bounding triangle), then one-by-one inserts points. As it inserts, it finds the triangle that contains the new point and subdivides that triangle. So do that recursively and you end up with a triangulation of your points. Then, at the end, remove all triangles that use the original vertices from the big super bounding triangle. Now, this recursive insert only produces a Delaunay triangulation if you do an edge-flipping step after each insert..the edge flipping makes sure that at each step you have a Delaunay-compliant triangulation. If you skip the edge-flipping step, the algorithm is easier to implement and you do end up with a triangulation...it is just that your triangulation could have some undesirable properties such as high aspect ratio, sliver triangles, maybe a poorly defined hull, etc.

The incremental approach to producing a triangulation is slow. Another approach, still brute force since it treats arbitrary points distributed randomly, is called divide and conquer. Recursively subdivide your domain until you end up with pieces that have 2 points or 3 points. It is easy to "triangulate" 2 points. You get an edge. It is easy to triangulate 3 points. You get a triangle. Then backing out of the recursion, the pieces are stitched together. You still have to do the edge flip step. This approach is more difficult to implement than the incremental approach. The benefit is that it is significantly faster. If you only have a few points, you may not need to worry about speed. But if you have a lot of points, you will feel the pain of the slowness of the incremental approach.

For reference:

Triangulation Algorithms and Data Structures If you're under ten thousand points, you may not care about speed as much.

Regarding the "supertriangle" approach, be aware that this does not always work. In practice, you detect the failure by determining that the polygon bounding the triangles is not convex. I recall running into this and posting to comp.graphics.algorithms many years ago. Jeff Erickson responded with an affirmative, that the supertriangle approach does not always work, and mentioned that this is a point-visibility issue. He described a general modification that effectively puts a point at infinity to deal with the visibility. Thus, there is a bit of extra work that must occur when using a supertriangle approach additional to the point insertion and edge swapping.

OK guys,, thanks so much for the help... I guess I am going with Delaunay... please forgive me for my lack of brightness, but it is kind of complicated for me to get the algorithm... I would appreciate if we could go like step by step with this... I suppose that first, I have to do something about the mentioned "super-triangle"... is that it?

So I just make up a triangle that I believe will cover the whole points cloud? I have already obtained the points that form the convex hull here in my program, if this might be of help... so.. I got the convex hull... next step would be...?


sry if i am asking for too much of detailed info.. and thanks for your patience... rates up for you guys ;)

Quote:

Original post by Dave Eberly Regarding the "supertriangle" approach, be aware that this does not always work. In practice, you detect the failure by determining that the polygon bounding the triangles is not convex. I recall running into this and posting to comp.graphics.algorithms many years ago. Jeff Erickson responded with an affirmative, that the supertriangle approach does not always work, and mentioned that this is a point-visibility issue. He described a general modification that effectively puts a point at infinity to deal with the visibility. Thus, there is a bit of extra work that must occur when using a supertriangle approach additional to the point insertion and edge swapping.

Dave, thank you for the comment. This is good, important information!

Try to google CGAL.
I have used it in fluid mechanics for discretization of areas.