Showing posts with label geometry. Show all posts
Showing posts with label geometry. Show all posts

Thursday, 2 July 2015

Identifying Concavity/Convexity in Polygons (for Dummies)

The following blog post is purely based off of this link: http://debian.fmi.uni-sofia.bg/~sergei/cgsr/docs/clockwise.htm. I like explaining things in my own way to make it more understandable, which is what I will attempt to here.

This blog post is about how to check whether a polygon is convex or not, (and subsequently, whether a polygon goes clockwise or counter-clockwise.) If you do not understand what convexity means, then I think a picture would be the best way to explain it:


As you can see from the above picture (which was taken off of the site I linked above), this polygon has concavity in all of its vertices except at (x5, y5).

If you do not understand what a clockwise vs counter-clockwise polygon is, then the following description will help: say if all of the edges of a polygon are represents as vectors pointing from one edge to the next. Did you visualize it? Are all the vectors going clockwise or counter-clockwise? That is basically the difference between a clockwise vs counter-clockwise polygon.

Now let us get back to determining the convexity of a polygon. This "isConvex" logic can be easily applicable in software engineering if you are (for example,) building an app that requires the user to manipulate some sort of polygon, though the polygon must always be convex. Using this "convexity" check will help in implementing this.

The test to check convexity of a vertex would be to check the cross product of the two adjacent sides that meet at that vertex.

A result of a cross product of two vectors would be another resultant vector that is 90 degrees from both of those two vectors. However, the vector could point either way along that axis which is  90 degrees from both of the two original vectors. By convention, we use the right hand rule to know which direction the resultant vector is pointing towards. This can be visualized in the below figure.

Figure 1

So by convention, if a is "behind" b like in this figure, then the cross product vector would go pointing up.

That said, let's say if we changed it so that the index finger in this illustration and the middle finger changed places, so that it looks something like this:

Figure 2. Like Figure 1, but where a is now pointing in b's direction, and b is pointing in a's direction.

Forgive me for my horrible drawing skills. As you can see, because the middle finger (which represents vector b) is now more "behind" the vector a (which is now more "in front/pointing towards the audience"), then that means the cross product will instead point downwards into the ground. This is just a convention mathematicians set up.

So, surprisingly enough, with this convention, we can actually test whether a polygon is convex or not. 

Figures 3 and 4

I will now describe how this test actually works. Basically, you do this test at each vertex by looking at its adjacent sides as vectors. Two vectors of a vertex is visualized above on the left-most picture (Figure 3) as the two red arrows, and the vertex is the yellow point.

You can do a cross product of these two vectors and see if the resultant cross product is going out of the page or into the page using the right hand rule.

By definition, the cross product of two vectors, both of which rely only on the x-y plane, can be simply defined as:
cross product = ((xi - xi-1),(yi - yi-1)) x ((xi+1 - xi),(yi+1 - yi)) = (xi - xi-1) * (yi+1 - yi) - (yi - yi-1) * (xi+1 - xi)
The points (Xi, Yi), (Xi-1, Yi-1), and (Xi+1, Yi+1) can all be seen in the two pictures I drew above.

Now, because vectors can be "moved" up or down on its line of direction, in the right-most picture (Figure 4), I moved the vector (that pointed from i-1 towards i) into the position that is shown using the blue arrow. I did this to make it easier to visualize how you can use the right hand rule in this test, where the thumb can be at the yellow vertex, and your middle and index fingers can be represented by the vector (i to i+1) and the blue vector.

Using the cross product equation above, we determine that the blue arrow would be vector a, and the red arrow that goes from  i to i+1 would be vector b. This corresponds with figure 2, so therefore, if you do the math for the specific example shown in Figure 4, the cross product is negative (going into the ground/page). A negative cross-product for a convex vertex (such as the one in Figure 4) means that the polygon is a clockwise polygon. This makes sense, since in figures 3 and 4, I drew the two red arrows going clockwise around the polygon!

In order to actually test for convexity versus concavity, you would have to do this similar test for all vertices of your polygon. If all vertices have the same sign, then that means your polygon is convex. If your polygon has a mixture of positive and negative cross products at the vertices, then that means the polygon must be concave at some points.

To determine exactly which points are convex or concave depends on whether you made the vectors of the polygon edges go around the polygon in a clockwise or counter-clockwise fashion. Like I said before, if your edge vectors around your polygon were clockwise, then convex points would result in negative-signed cross products. If the polygon was clockwise and you evaluate the cross product at a certain vertex which gave you a positive-signed cross product, then you can conclude that vertex would be concave.