Jump to content
  • Advertisement
Sign in to follow this  
NickW

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
I was going to say the same. I delaunay triangulation is not the same a the triangulation of a polygon.

Share this post


Link to post
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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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 NickW
The 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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!