#### Archived

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.

## 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 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.

GA

##### 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 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 on other sites
I''m still looking for the same ..
so if you find something please mail me :
zordan_ehrwald@gmx.net

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.

• 10
• 13
• 52
• 11
• 15