#### Archived

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

# how do I break a polygon into triangle

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

## Recommended Posts

What algorithm should I use if I want to break a concave polygon into triangle?

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

This should work.

GA

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 9
• 9
• 9
• 14
• 12
• ### Forum Statistics

• Total Topics
633297
• Total Posts
3011251
• ### Who's Online (See full list)

There are no registered users currently online

×