reflex vertex
Author
I'm trying to code ear-clipping triangulation but ran into an understanding problem regarding reflexive vertices. I'm following "Triangulation by Ear Clipping" by Eberly.
How would I determine if I'm finding the interior angle or the exterior? I've googled a lot and have seen sites refer to LeftOn function which I see is a bool function that states wither the vertex is reflex or convex but I not sure what it's supposed to do since there is no code shown for the function.
I would could use the help.
[Edited by - Asem on January 25, 2009 12:01:23 AM]
Quote:Original post by AsemYou can get the signed angle between two 2-d vectors by using (e.g.) atan2(), but that's not really necessary in this case. Since all you're really concerned with is whether a given edge takes a 'left' or 'right' turn with respect to the previous edge, all you really need is the perp-dot product. (Or so I assume. I haven't actually looked at the article - there may be more to it than that.)
I'm trying to code ear-clipping triangulation but ran into an understanding problem regarding reflexive vertices. I'm following "Triangulation by Ear Clipping" by Eberly.
I'm not sure what angle it's looking for since if it's reflexive there's an angle greater than 180 if convex it's less than 180. I though getting the angle between the lines would work but I can only get angles from 0 to 180.
It's not clear to me from your post exactly what your problem is so I'll try to respond to both issues I see.
If you have a simple (non-convex, non-self-intersecting) polygon in 2D, assume your representation is an ordered list of coordinate tuples (vertices).
Problem 1: what is the orientation of the polygon. If I start at any vertex, I need to know if I go to the next vertex, whether the interior is on my left or my right.
A fairly simple solution is to find the vertex with minimum x coordinate, and simply look at the orientation of its outgoing edges. If the next vertex in the list is ABOVE the previous vertex in the list, then the orientation is clockwise, and anti-clockwise if not.
Problem 2: In the ear-clipping algorithm, what happens at reflex vertices?
Consider the case of a circle of vertices, with one vertex pulled into the center of the circle.
that vertex is both reflex, and will always have an ear incident to it.
So there is no problem, you still detect ears the same way as always; find triangles defined over three sequential vertices that are interior to the polygon, and which contain no other vertices.
Good luck
If you have a simple (non-convex, non-self-intersecting) polygon in 2D, assume your representation is an ordered list of coordinate tuples (vertices).
Problem 1: what is the orientation of the polygon. If I start at any vertex, I need to know if I go to the next vertex, whether the interior is on my left or my right.
A fairly simple solution is to find the vertex with minimum x coordinate, and simply look at the orientation of its outgoing edges. If the next vertex in the list is ABOVE the previous vertex in the list, then the orientation is clockwise, and anti-clockwise if not.
Problem 2: In the ear-clipping algorithm, what happens at reflex vertices?
Consider the case of a circle of vertices, with one vertex pulled into the center of the circle.
that vertex is both reflex, and will always have an ear incident to it.
So there is no problem, you still detect ears the same way as always; find triangles defined over three sequential vertices that are interior to the polygon, and which contain no other vertices.
Good luck
Author
I'll try to be a little more clear though you guys gave me something to think about.
in the article there's this statement here:
I used the dot product to get the angle between the 2 edges shared by one vertex (all together 3 vertices). The problem is , depending on the polygon, I will either get the interior angle or exterior angle just by regularly iterating through triple vertices. If I get the exterior angle than I should compensate for the actual interior angle.
Although if that's the case than I guess I wouldn't have to really determine the reflex by the interior angle but I'm just trying to follow the article.
That was my reason to look for the interior angle. It seems to be meant to keep track of the reflex and convex vertices in the article though.
in the article there's this statement here:
Quote:Triangulation by Ear Clipping article:
A reflex vertex is one for which the interior angle formed by the two edges
sharing it is larger than 180 degrees. A convex vertex is one for which the
interior angle is smaller than 180 degrees.
I used the dot product to get the angle between the 2 edges shared by one vertex (all together 3 vertices). The problem is , depending on the polygon, I will either get the interior angle or exterior angle just by regularly iterating through triple vertices. If I get the exterior angle than I should compensate for the actual interior angle.
Although if that's the case than I guess I wouldn't have to really determine the reflex by the interior angle but I'm just trying to follow the article.
That was my reason to look for the interior angle. It seems to be meant to keep track of the reflex and convex vertices in the article though.
OK jyk's answer actually addresses your issue.
If you have a sequence of three vertices and you want to know the described at the middle one, you can take the dot product of the normalized incident edges to get the cosine of the angle. Then take a vector perpendicular to one of the edges and dot it with the other edge; depending on whether the result is positive or negative you can tell if it is a left or right turn.
Also, the planar cross product will give you the same information, take the two normalized incident edges and arrange them into a 2x2 matrix. Take the determinant of that matrix and you will get the sin of the angle. So if the value is positive then the angle is less than pi radians, and if it is negative then the angle is more.
On a more general note, in computational geometry you should avoid actually computing angles wherever possible. These are expensive operations that are rarely necessary.
If you have a sequence of three vertices and you want to know the described at the middle one, you can take the dot product of the normalized incident edges to get the cosine of the angle. Then take a vector perpendicular to one of the edges and dot it with the other edge; depending on whether the result is positive or negative you can tell if it is a left or right turn.
Also, the planar cross product will give you the same information, take the two normalized incident edges and arrange them into a 2x2 matrix. Take the determinant of that matrix and you will get the sin of the angle. So if the value is positive then the angle is less than pi radians, and if it is negative then the angle is more.
On a more general note, in computational geometry you should avoid actually computing angles wherever possible. These are expensive operations that are rarely necessary.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
