Jump to content
  • Advertisement


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.

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

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

I hope this will work.

Visit our homepage: www.rarebyte.de.st


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!