Jump to content
  • Advertisement


This topic is now archived and is closed to further replies.


Polygon triangulation

This topic is 6905 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

Does anyone know if there''s any good, nice, fast, free polygon triangulation code that works for complex polygons around, or even a readable document on the subject? I could only find weird ultra-mathy docs with strange pseudocode and stuff that only works for simple polygons (mostly "ear-cutting").

Share this post

Link to post
Share on other sites
You have the 2d - vertices v0, v1, ... vn

Let''s say the vector v0v1 points to the right.

Step 1:

First you should determine if the polygon is "above" v0 or "below" v0, I mean, if the line loop v0v1v2...vnv0
is left-handed or right-handed. Therefor you calculate the vectors v0v1, v0v2, ... v0vn. Then normalize these vectors: vu = v/sqrt(v.x^2 + v.y^2) and add them: v0v1u + v0v2u + v0v3u + ... + v0vnu. If this vector, I''ll call it s, is on the left hand of v0v1, the line loop is left-handed:

v0v1.x*s.y - v01v1.y*s.x > 0 -> left-handed
v0v1.x*s.y - v01v1.y*s.x < 0 -> right-handed

Step 2:

Now search for a start corner with an angle less than 180°.
You could determine this:
a = v(i+1) - vi
b = v(i-1) - vi
(for i=0 i-1=n and for i=n i+1=0)
If a.x*b.y - a.y*b.x has the same sign as v0v1.x*s.y - v01v1.y*s.x, the angle is less than 180°.

Now search for the next angle which is not less than 180°.
If you have found one, you can cut off the convex polyon with a line from the vertex before your start corner to the vertex with the > 180° angle. You can split the convex polygon into triangles with a simple algorithm. With the rest of the concave polygon you make the same thing from step 2 downward.
Do this until there''s only one convex polygon left.

I hope this works.

Visit our homepage: www.rarebyte.de.st


Share this post

Link to post
Share on other sites
Hmm, that looks a lot like ear-cutting (only it searches for convex polygons instead of triangles, which is good), and I don''t think it''ll work for complex polygons. Thanks anyways - I think I might just forget complex polygons (they could mean trouble with texture coordinates and collisions).

Share this post

Link to post
Share on other sites
Howdy Painless,

This is not universally useful, but if you''re using OpenGL you could check out gluTesselator (yes, its spelt wrong) objects... I believe this is useful for auomatically splitting up complex polys (convex and concave).

I''m not exactly sure if it splits them into triangles though... oh well

squirrels are a remarkable source of protein...

Share this post

Link to post
Share on other sites
I''m still looking for the same ..
so if you find something please mail me :

I bought a algho-book for c there ... but i havent read it totaly yet. But when I find something about i let ya know.

PS. look for Delauny-Triangulation ... this is how the triangulation chapter is called.

Share this post

Link to post
Share on other sites

  • Advertisement

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!