article

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.

*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.

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

Or view it as a repository at BitBucket

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:

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

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

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

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**

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 takes N^{2}/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**.

*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; } }

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.

Consider this illustration, to help explain this selection process.

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

info@hofware.nl | ||

Telefoon | 06 4072 2423 | |

KvK | 62595407 | |

Hofware 2015 - Hoflaan @ Arnhem

Foto 'John Frost Bridge' door Maarten Takens