Sign in to follow this  

Converting a polygon into the least number of triangles possible?

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

Title sums it up. I'm looking for a simple/fast method of converting a polygon into the least number of triangles possible.

Thanks in advance.

Share this post


Link to post
Share on other sites
The ear clipping algorithm is simple to implement on paper, but producing a reliable method of triangulating concave polygons with floating point coordinates is another story. I found that the difference between comparing floats with < and <= would often be the difference between the algorithm working perfectly or producing mess. You've also got to worry about self-intersecting polygons, which I've found is an issue with all concave polygon algorithms, as the difference between concave and self-intersecting can lie inside floating point tolerance.

Share this post


Link to post
Share on other sites
Alright I've read through the Ear Clipping paper and I think I understand what's going on here. I do have one question though:

[img]http://i298.photobucket.com/albums/mm265/ahlywog/Triangles.jpg[/img]

The paper is talking about "A [i]reflex vertex[/i] is one for which the interior angle formed by the two edges sharing it is larger than 180 degrees. A [i]convex vertex[/i] is one for which the interior angle is smaller than 180 degrees." Say I'm looking at triangle 4, 1, 2. Iterating through all my vertex's shows that 4-1-2 has no other vertex's in it so it would pass initial ear triangle tests. But 4-1-2 is not part of the actual polygon. How do I test my potential ear triangles to determine if they're reflex or convex?

Share this post


Link to post
Share on other sites
You have to categorise the polygon as either clockwise or counterclockwise. First, you find a vertex which you can guarantee is convex. The best way of doing this is to choose the vertex with the minimum x coord, and minimum y coord if there are ties. Now you do a convexity check on the triangle around that vertex, which can be done by calculating the triangle's signed area. If area > 0, the triangle is counterclockwise. Area < 0 = clockwise.

Once you have the winding of a known convex vertex, you can determine if any vertex is convex, as all convex verties have the same winding, and all concave vertices have the opposite winding.

Share this post


Link to post
Share on other sites
Alright, A long time getting back to this, Busy with school. Ugh.

So I've found the following (http://2000clicks.com/MathHelp/GeometryTriangleAreaVector3.aspx):

In the x-y coordinate plane, the signed areas are given by
A[sub]1[/sub] = (x[sub]3[/sub] y[sub]2[/sub] - x[sub]2[/sub] y[sub]3[/sub])/2
A[sub]2[/sub] = (x[sub]1[/sub] y[sub]3[/sub] - x[sub]3[/sub] y[sub]1[/sub])/2
A[sub]3[/sub] = (x[sub]2[/sub] y[sub]1[/sub] - x[sub]1[/sub] y[sub]2[/sub])/2

So that's in X-Y. I can't find a good example of what it would be in X-Y-Z.

Share this post


Link to post
Share on other sites
The trick to solving most 3D planar problems is to just ignore one of the coordinates and treat the problem as a 2D one. Consider the normal to the plane the vertices lie in, and discard the axis with the greatest absolute value. For example, if the normal is (0,1,0), you discard the y axis and work in the x,z plane. Alhough you could actually discard any axis as long as it's normal component is not on, or close to zero.

Keep in mind if the plane is not axis aligned (and it usually isn't), then measurements in the 2D plane are different than in 3D. So when you calculate the area of the triangle around your vertices in 2D, it's not the actual area in 3D space, but it still retains all it's important properties. (For determining winding, etc).

Being able to address vectors with an array subscript is useful here. So in 2D, a 3D point is given by (P[iX], P[iY]), where iX,iY = 1,2 (x axis ignored), 2,0 (y axis ignored) or 0,1 (z axis ignored).
Or you could just copy your vertices in memory first. I actually employ a 2D iterator object that can be constructed from an array of 3D points and a normal.


Share this post


Link to post
Share on other sites
[code]
float Signed_Area(vec3 Vec1, vec3 Vec2, vec3 Vec3)
{
return (float)(0.5 * (-Vec2.x * Vec1.y + Vec3.x * Vec1.y + Vec1.x * Vec2.y - Vec3.x * Vec2.y - Vec1.x * Vec3.y + Vec2.x * Vec3.y));
}
[/code]

I got the idea for this here [url="http://mathworld.wolfram.com/TriangleArea.html"]Wolfram.com[/url]. obviously it's not checking to see if anything is zero. I'll figure something out for that.

Share this post


Link to post
Share on other sites

This topic is 2336 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this