My question is focused around triangulation. I was studying and implementing various 2D surface triangulation algorithms. The one I am working on implementing right now is ear-clipping.
Reading an article on ear clipping I saw the author characterizing each vertex Pi of a set of Vertices P as either:
1)concave: if the interior angle formed by the edge from Pi-1 to Pi+1 is less than 180 degrees
2) reflexive: if the interior angle formed by the edge from Pi-1 to Pi+1 is more than 180 degrees
The definition is clear enough. But how do you detect such a thing. I have not been able to find a clear suggestion on the net as to the optimal algorithm for doing this.
In my application I get a set of vertices which form a 2D surface (polygon). They are ordered counter-clockwise so the interior of the polygon is always to the right of each edge being formed. (If I did not have that I guess I would have to resort to ray casting)
I did make an algorithm to check if every vertex is concave or reflexive but I don’t think it’s optimal. That’s why I am asking if there is a standard way to do this.
Thanks for taking the time to read my post.
I don’t know of a standard way, but here is what I’m doing:
First you need some “reference”, to know which vertices are really on the convex hull. Simply compute the bounding box of the polygon. All vertices that touch the bounding box are definitely on the convex hull (in your terms “reflexive”).
This is especially important, when you do not know the orientation and winding order of a polygon. With some data-sets that’s the case.
Now you simply take vertex Pi and Pi+1 and put a plane through it (using the normal of the polygon as an additional vector, your plane will then be defined by the points Pi, Pi+1 and Pi + Normal).
Now check if there is ANY vertex from the polygon in front of the plane. If the vertex Pi is convex, ALL vertices are behind the plane. That’s it. Repeat it for every vertex and you will find out which ones are convex and which are concave.
Of course don’t forget that every vertex has two neighbors and therefore you need to check two planes, etc., so there are a few more implementation details, but you should be able to figure that out easily.
Thanks Jan, pointing out a method for handling data sets which have unknown orientation will really help. I will have to deal with such data sets soon.
But say for a set of vertices with anti-clockwise orientation and the interior of the polygon on the right. For such a case the best way to see which vertex is concave and which reflexive would be via crossproducts right?