Border finder (Convex Hull)

article

Rubber band algorithm

Tags: Graham Scan Insertion Sort Demo  GM 2015 

1Introduction

The convex hull is often refered to a the "Rubber band" algorithm. If you hammer nails into a wooden board, and put a rubber band around it, the rubber band will form the convex hull.

The convex hull is the smallest envelope containing all points of a given set.

rubber band - convex hull

Imagine a rubber band around a set of nails

A very common solution to compute this envelope, is the Graham Scan. Below you will find pointers and examples to start building for yourself.


2Convex Hull in Action

Your browser doesn't support HTML5 canvas.

Source Code

For GameMaker fans, you can download the above demo as GM source code here

Or view it as a repository at BitBucket


3Graham Scan

To determine the convex hull we perform a Graham Scan, invented by Graham, R.L. (1972). There are a lot of alternative algorithms but the Graham is fast and easy to understand.

The scan approaches this in 4 steps:

  1. Pick the lowest point as point 0
  2. Calculate the polar-angles to all other points
  3. Sort the points in ascending polar-angle order
  4. Perform a counter-clockwise scan, saving only convex steps

You can view a very good explenation from Princeton University at Youtube

Video - scan in action


4HowTo Code

Assume a randomly destributed 2D point field, with N points.

Pick the lowest point

As a starting point p0 it is efficient to pick the lowest Y-position first. It is for certain on the hull and requires only N steps to determine.

Each point is checked once, the one with the largest Y is picked a point p0

Polar angles and Sort

Calculate the angle between each point and p0 and store it to an array.

Next, sort the array in increasing order of polar angle. A very simple algorithm to do this is insertion sort


Insertion Sort

Insertion sort takes N2/4 (quadratic) time on average. But it takes just N (linear) time in the best case.

The best case occurs when the array is largely already ordered. We can exploit this, for instance in the demo above. Every frame it sorts the points, but only the first time happens in quadratic time. After that it takes just linear time.

order

Insertion sort example

Insertion sort is extremely simple to code, does not require helper arrays (in place), and is realy fast for small N:

// start insertion sort
for (var i=1; i < N; i++) 
{
    for (var j = i; j > 0; j--)
    {
        // Moving from right to left, exchange i with each larger entry to its left
        if (polarAngle[ j ] < polarAngle[ j-1 ]) 
            Swap(j, j-1);
        else
            break;
    }    
}
					

Counter Clockwise Scan

Next, starting at point p0, we investigate each point in order of polar angle. Every time the scan steps from one node to the next, it determines if the resulting bend is convex (left-hand turn) or concave (right-hand turn).
If the bend is concave the second-to-last node is considered to be not on the hull. After removing it, we check if all bends are convex. If not we keep removing previously found points from our hull, until all bends convex again.

order

Consider this illustration, to help explain this selection process.


Example code

Have a look at the code example of the the graham loop at BitBucket if you seek further examples.