#### Archived

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

# Triangulate a concave polygon?

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

## Recommended Posts

I am using Direct3D and need to triangulate a concave polygon (since D3D only supports triangles doh!). It''s easy enough if the poly is convex, so a concave -> convex algorithm would also help me. Cheers!. John.

##### 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 you have left a convex polygon.

I hope this will work.

GA

• 10
• 13
• 52
• 11
• 15