Say you have \(N\) points on a Euclidean plane. You want to find the polygon with the smallest area that can be formed connecting a subset of those points such that all the points are contained within the polygon.
In reality, you get this if you put a rubber band about all the points. It will naturally form the convex hull (if it is tight).
Knowing the convex hull is useful, for example, for rerouting around known obstacles.
As you traverse the convex hull in a counter clockwise fashion, the polar angle only increases.
The hull can be found recursively.
- Start from the lowest (y-coordinate) point.
- Sort all the other points by polar angle.
- Connect to the next point. Now you have a line.
- Consider the next point. Did you make a CCW turn to get to it? If not, discard the current point consider the next candidate, and so on.
To check for counterclockwiseness, I’m too lazy to write the details. The idea is that the 3 points for a triangle, and two sides can be considered to be vectors. Pick appropriate sides and take the cross product (using the coordinates). Counterclockwiseness will be determined by the sign of the result.
This algorithm is the Graham scan.
The complexity is \(O(N\lg N)\) - mostly due to the sorting. The rest of the algorithm is linear, because each point is considered at most twice (either in a left turn or a right turn).
There are some nuances I neglected (e.g. if you have collinear points).