Polygon
Convexity |
Download Applet with Source (18kb)
After searching for a simple algorithm for checking if a (simple!) polygon is convex, I came across a quite simple but interesting algorithm. (A simple polygon does not contain any holes and the boundary of the polygon does not cross itself). First two easy definitions:
Convex
Set: A set P is convex if for every two points p1, p2
within this set, the straight line between them is also completely within
this set. |
Convex
Polygon: A simple polygon P is convex if its interior is a convex
set. |
For example:
Ok, so to check the convexity of a polygon, you can think about it like this: If you move along the sides of the polygon and you just have to move to the left or the right, then it is convex. If you have to change the direction at least once, then it is not convex. In this way it doesn't matter if you walk along the sides in clockwise or counterclockwise direction.
Sounds pretty obvious but how to find out if the next point is right or left from the current polygon edge? Have a look at following image: p and t are two consecutive vertices of the polygon.
The
line g is the line through them, we can write it in a form like this:
So you can calculate all points u on the line g by inserting
any r values you like. Let's eliminate r...
The
function f has following properties: f(u) = 0
if the next polygon vertice u is on the line; f(u)
> 0 if the next polygon vertice u is right from the line g
and f(u) < 0 if the next polygon
vertice u is left from the line g. "Left" and "Right"
depends on the direction of vector v, so it depends on going along the polygon
clockwise or counterclockwise.
Next applet shows you exactly this for three points. You can play around a bit
:-)
So to check a complete polygon is very easy - just walk along all vertices and check if the direction changes. This is implemented in the applet belonging to the article about filling arbitrary polygons on my site, but here is the source:
/* |
This site is part of Sunshine's Homepage