Skinny Triangles
Author
I am working with a polygon triangulation algorithm and was wondering what would be a good method of finding out if the triangles given are too skinny also a good method to even(?) them out? Make them less skinny?
I use c++ in case it's relevant.
Thanks.
A triangle is skinny iff one of its angles is very large (close to Pi).
You can generate a triangulation that avoids skinny triangles by using the constrained Delaunay triangulations from CGAL.
You can generate a triangulation that avoids skinny triangles by using the constrained Delaunay triangulations from CGAL.
Author
Though delaunay triangulations don't generate triangles inside an outline of vertices it just uses all the vertices available which would be bad for my case.
With that information I am still trying to think of a way to even the angles/vertices/edges out. Perhaps open up or close the other two vertices until the offending angle/vertice no longer offends?
What about triangles with almost parallel sides?
With that information I am still trying to think of a way to even the angles/vertices/edges out. Perhaps open up or close the other two vertices until the offending angle/vertice no longer offends?
What about triangles with almost parallel sides?
The idea of Delaunay triangulation is good, but constrained Delaunay is messy, and you can get Delaunay quality using a slightly modified polygon triangulation algorithm. Read on.
So, what type of triangulation algorithm are you using? My recommendation is to use an ear-clipper, but with a modification. Instead of testing candidate ears by looking to see if any vertex is inside the ear triangle, replace that point-in-triangle test with a test to see if a vertex is inside the circumcircle of the triangle. The cirumcircle, or cirumscribed circle, is a circle that contains the 3 vertices of the triangle. This circumcircle test actually represents a Delaunay constraint, e.g., it is related to Delaunay triangulation theory. The Delaunay constraint has a characteristic of prefering non-skinny triangles. So, if you make this relatively simple change to an ear-clipping algorithm, you will naturally get triangles that are less skinny. Trust me, it works. In our code here, we used to use a traditional ear-clipper, which yielded many problematic and skinny triangles. Substituting the Delaunay ear constraint works beautifully. If you google "circumcircle" you will find links to source code for computing the circumcircle of a triangle.
One thing to watch out for. In some cases, you may not find an ear that is Delaunay-compliant. In this case, you'll have to use a different heuristic and my recommendation here is to use the traditional point-in-triangle test but modify to pick the ear with the smallest slenderness ratio, where slenderness is define to be the ratio of area to circumference (a skinny triangle will have a small area but a large circumference). This should only be a fallback case, since Delaunay-compliant ears will give you the highest quality triangulation (in terms of minimizing skinny triangles). (Note that while you have to do a little computation to find the circumcircle, the actual point-in-circle tests are much cheaper than the traditional point-in-triangle tests, so this approach should not be slower, and may be faster, than traditional point-in-triangle ear clipping.)
An example of where you may not find such a case...if several of your points are actually on the same circle, then around that circle you will not find any Delaunay-compliant ears (except by floating point roundoff luck).
There other caveats...I won't describe here in detail, but if you find weird behavior, inconsistent behavior when testing for point in circle or point in triangle, then look into robust predicates and google "Jonathan Shewchuk robust predicates." This is a complexity...you may find that you never have any trouble with the above ideas I've described. But, if you test a thousand random polygons, you may find that 2 or 3 of them fail for reasons that are hard to track down. If you need the highest degree of robustness, you will need to look into this complexity.
Hope that helps!
So, what type of triangulation algorithm are you using? My recommendation is to use an ear-clipper, but with a modification. Instead of testing candidate ears by looking to see if any vertex is inside the ear triangle, replace that point-in-triangle test with a test to see if a vertex is inside the circumcircle of the triangle. The cirumcircle, or cirumscribed circle, is a circle that contains the 3 vertices of the triangle. This circumcircle test actually represents a Delaunay constraint, e.g., it is related to Delaunay triangulation theory. The Delaunay constraint has a characteristic of prefering non-skinny triangles. So, if you make this relatively simple change to an ear-clipping algorithm, you will naturally get triangles that are less skinny. Trust me, it works. In our code here, we used to use a traditional ear-clipper, which yielded many problematic and skinny triangles. Substituting the Delaunay ear constraint works beautifully. If you google "circumcircle" you will find links to source code for computing the circumcircle of a triangle.
One thing to watch out for. In some cases, you may not find an ear that is Delaunay-compliant. In this case, you'll have to use a different heuristic and my recommendation here is to use the traditional point-in-triangle test but modify to pick the ear with the smallest slenderness ratio, where slenderness is define to be the ratio of area to circumference (a skinny triangle will have a small area but a large circumference). This should only be a fallback case, since Delaunay-compliant ears will give you the highest quality triangulation (in terms of minimizing skinny triangles). (Note that while you have to do a little computation to find the circumcircle, the actual point-in-circle tests are much cheaper than the traditional point-in-triangle tests, so this approach should not be slower, and may be faster, than traditional point-in-triangle ear clipping.)
An example of where you may not find such a case...if several of your points are actually on the same circle, then around that circle you will not find any Delaunay-compliant ears (except by floating point roundoff luck).
There other caveats...I won't describe here in detail, but if you find weird behavior, inconsistent behavior when testing for point in circle or point in triangle, then look into robust predicates and google "Jonathan Shewchuk robust predicates." This is a complexity...you may find that you never have any trouble with the above ideas I've described. But, if you test a thousand random polygons, you may find that 2 or 3 of them fail for reasons that are hard to track down. If you need the highest degree of robustness, you will need to look into this complexity.
Hope that helps!
Another comment. If you have a case where a skinny triangle is unavoidable (e.g., the source polygon itself is skinny and has long edges), your only solution may be to subdivide long edges...create new vertices, then re-triangulate.
Author
I tried going by the 'skinny triangles are the result of one angle being almost pi' to remove the offending triangles.
This is the code to find to check each angle and remove the triangle if the angle is too big. Though trying it with large angles doesn't work and trying it with small ones removes most of the triangles, among the exceptions the ones I want removed :S.
Am I doing something wrong?
Here's an image of the triangles with the ones I want removed circled in red.
http://img20.imageshack.us/img20/5492/offendingtriangles.jpg
This is the code to find to check each angle and remove the triangle if the angle is too big. Though trying it with large angles doesn't work and trying it with small ones removes most of the triangles, among the exceptions the ones I want removed :S.
Am I doing something wrong?
bool PlayState::FixAngles(b2Vec2 v0, b2Vec2 v1){ double n1 = sqrt(v0.x * v0.x + v0.y * v0.y); double n2 = sqrt(v1.x * v1.x + v1.y * v1.y); double angle = acos((v0.x * v1.x + v0.y * v1.y)/(n1*n2)); if(angle > DegtoRad(120)){ return false; } return true;}Here's an image of the triangles with the ones I want removed circled in red.
http://img20.imageshack.us/img20/5492/offendingtriangles.jpg
Even if you don't use the constrained Delaunay that I suggested (which I still think could be made to work), you can still use flipping to fix the skinny triangles you have.
Basically, whenever you have two triangles ABD and BCD that share an edge and whose union is convex, you can replace them with ABC and ACD. This will be a good idea when C is inside the circle that passes through A, B and D.
These flips would fix all the skinny triangles in your example.
I would simply go around your triangulation several times trying to identify places where you can use flipping to improve the situation.
Basically, whenever you have two triangles ABD and BCD that share an edge and whose union is convex, you can replace them with ABC and ACD. This will be a good idea when C is inside the circle that passes through A, B and D.
These flips would fix all the skinny triangles in your example.
I would simply go around your triangulation several times trying to identify places where you can use flipping to improve the situation.
Author
Alright I'll try it out though that still requires me to find out the size of each angle which was the thing that first brought me back here. How do I fix my code ^_^'?
I don't see anything wrong with your code. Perhaps you can try to find an example of input for which it doesn't do the right thing...
Author
Well I tested it with each of the angles of a triangle and they don't add up to 180(After converting to degrees). They add up to about 50. I tried with other triangles and it didn't go much above that either. They should add to 180 shouldn't they? Unless I am not understanding what this equation is about :S.
bool PlayState::FixAngles(b2Vec2 &v0, b2Vec2 &v1, b2Vec2 &v2){ double n1 = sqrt(v0.x * v0.x + v0.y * v0.y); double n2 = sqrt(v1.x * v1.x + v1.y * v1.y); double angle = RadtoDeg(acos((v0.x * v1.x + v0.y * v1.y)/(n1*n2))); if(angle < 5){ return false; } return true;}float PlayState::RadtoDeg(float radians){ const float pi = 3.14159; return radians * (180/pi);}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
