Polygon Triangulation
Author
I'm looking for an algorithm to turn a simple 2-D polygon (ordered set of continuous non-intersecting vectors) into a set of triangles. The algorithm should also be able to support holes in the polygon, which are also simple polygons. I realize that this is a topic which has been under discussion a lot, but I have not been able to find a place that has an easy to follow implementation of an algorithm.
Google Delaunay Triangulation. That is what you want. Lots of descriptions of the technique if you want to roll it yourself. The basics is easy to get working, the details can get tricky depending on your requirements, like requiring certain edges or specific triangle area restrictions.
The key researcher in my opinion is Johnathan Shewchuk. He has made his Triangle program available as source and it is very robust. http://www.cs.cmu.edu/~quake/triangle.html
That should give you plenty to get started.
The key researcher in my opinion is Johnathan Shewchuk. He has made his Triangle program available as source and it is very robust. http://www.cs.cmu.edu/~quake/triangle.html
That should give you plenty to get started.
Quote:Original post by JeffLander
Google Delaunay Triangulation. That is what you want.
That is incorrect. Delaunay triangulation is not related to what the poster is asking.
Look at the following site: http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html
The references mentioned on that page might be useful.
I was going to say the same. I delaunay triangulation is not the same a the triangulation of a polygon.
A "constrained Delaunay triangulation" allows you to specify edges that must occur in the triangulation, so in fact you can use a Delaunay approach to triangulate polygons. However, this is definitely not the way to go.
The triangulation in the GEM reference that Aryabhatta provided is intended to be a "fast" triangulation in the sense of asymptotic order. It is O(n log*(n)), where log*(n) is the "iterated logarithm" (see "Algorithms" by Cormen et al.). In practice, log*(n) is effectively a constant, so the triangulation is effectively linear. The algorithm, though, requires a lot of patience to implement and get it right.
Unless you have n on the order of 100,000 or larger, I would recommend just using a simple ear-clipping algorithm. This is easy to implement.
The triangulation in the GEM reference that Aryabhatta provided is intended to be a "fast" triangulation in the sense of asymptotic order. It is O(n log*(n)), where log*(n) is the "iterated logarithm" (see "Algorithms" by Cormen et al.). In practice, log*(n) is effectively a constant, so the triangulation is effectively linear. The algorithm, though, requires a lot of patience to implement and get it right.
Unless you have n on the order of 100,000 or larger, I would recommend just using a simple ear-clipping algorithm. This is easy to implement.
Quote:Original post by Anonymous Poster
I was going to say the same. I delaunay triangulation is not the same a the triangulation of a polygon.
Well, it can be. The Delaunay triangulation of the points of a convex polygon is the best minimal triangulation of that polygon (for a particular reasonable definition of "best"). But yeah, as soon as you go concave, the Delaunay triangulation is no longer useful.
Author
With a little bit of modification, the code that Aryabhatta linked to seems to work ok. From what I can tell, it translates the polygon in to monotonic polygons using trapazoid division? Anyway, this code should work fine since I don't anticipate my polygons to get over 500 vertices.
Also, it would seem that finding the "best" triangulation of a convex polygon is trivial.
Also, it would seem that finding the "best" triangulation of a convex polygon is trivial.
Well it did not say if the polygon was convex or not, but I was assuming the method was suppose to handle polygons with holes.
Guess what when you unify a polygon with a hole by making cuts, you end up with a general concave polygon.
So yes the Deluanay triangulation will not work
I would read the book Computational; Geometry in C or C++
Find the method Triangulation by ear cutting.
Quote:Original post by NickWI remember correctly most triangulation method, will cut polygons will hole as a preprocess phase in order to removes holes.
The algorithm should also be able to support holes in the polygon, which are also simple polygons.
Guess what when you unify a polygon with a hole by making cuts, you end up with a general concave polygon.
So yes the Deluanay triangulation will not work
I would read the book Computational; Geometry in C or C++
Find the method Triangulation by ear cutting.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
