# Polygon Triangulation

This topic is 4709 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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.

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by JeffLanderGoogle 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.

##### Share on other sites
I was going to say the same. I delaunay triangulation is not the same a the triangulation of a polygon.

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by Anonymous PosterI 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.

##### Share on other sites
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.

##### Share on other sites
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.
Quote:
 Original post by NickWThe algorithm should also be able to support holes in the polygon, which are also simple polygons.
I remember correctly most triangulation method, will cut polygons will hole as a preprocess phase in order to removes 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.

1. 1
Rutin
45
2. 2
3. 3
4. 4
5. 5

• 10
• 28
• 20
• 9
• 20
• ### Forum Statistics

• Total Topics
633407
• Total Posts
3011699
• ### Who's Online (See full list)

There are no registered users currently online

×