contact Me

Use the form on the right to contact me.

You are welcome, to contact me regarding the topics of this page, my open source projects, or my work. Please use the contact form and leave a valid email address for me to respond to.

Thank you.

Egidestr. 9
44892 Bochum
Germany

/brain/dump

Random thoughts, bright ideas and interesting experiments. In short the ramblings of a fulltime nerd.

 

Calculate a convex hull - The QuickHull algorithm

Jakob Westhoff

In need of a fast and efficient way of calculating the convex hull of a point set, I stumbled across the QuickHull algorithm, after doing some research. This algorithm is a divide and conquer approach to solve the given problem, which is quite efficient in the average case. The following article gives an introduction into convex hulls and the QuickHull algorithm itself. Furthermore a implementation of it in PHP is presented for download.

Convex Hull

The Wikipedia article about the convex hull draws a quite intuitive picture of this rather mathematical construct:

For planar objects, i.e., lying in the plane, the convex hull may be 
easily visualized by imagining an elastic band stretched open to encompass
the given object; when released, it will assume the shape of the required
convex hull.

As always a picture says more than thousand words. Therefore the following picture should make the intuition a lot clearer.

A set of points enclosed by a rubber band. (Image created by wikimedia commons user Maksim and released under public domain)

A set of points enclosed by a rubber band. (Image created by wikimedia commons user Maksim and released under public domain)

As you can see the convex hull in two dimensional space is the minimal polygon, which encloses all of the given points.

QuickHull

Instead of choosing the naive solution to do a simple linear comparison of all points to find the ones which are lying at the outer most edge, QuickHull uses a divide and conquer approach similar to the QuickSort algorithm. Hence its name.

There are quite a few other efficient algorithms to calculate a complex hull, like Graham-Scan or Jarvis-March. I decided to use QuickHull because benchmarks showed it is quite fast in most average cases, as well as its recursive nature allows a fast and yet clean implementation.

QuickHull performs its calculations in a recursive manner on intelligently chosen subsets of the initial set of points.

Initial input

example1.png

The initial input to the algorithm is an arbitrary set of points. Under average circumstances the algorithm is quite fast. There are however cases, like highly symmetric point sets (points lying on a circumference for example), which make processing a lot slower.

 

First two points on the convex hull

example2.png

Starting with the given set of points the first operation done is the calculation of the two maximal points on the horizontal axis. These two points are guaranteed to be part of the convex hull polygon.

 

Recursively divide

example3.png

Next the line formed by these two points is used to divide the set into two different parts. Everything left from this line is considered one part, everything right of it is considered another one. Both of these parts are processed recursively.

To show the further steps of the algorithm only the left point set is used as an example. The right point set is handled exactly the same way.

 

Max distance search

example4b.png

To determine the next point on the convex hull a search for the point with the greatest distance from the dividing line is done. This point, together with the line start and end point forms a triangle.

 

Point exclusion

example4.png

All points inside this triangle can not be part of the convex hull polygon, as they are obviously lying in the convex hull of the three selected points. Therefore these points can be ignored for every further processing step.

 

Recursively divide

example5.png

Having this in mind the recursive processing can take place again. Everything right of the triangle is used as one subset, everything left of it as another one.

 

Abort condition

example7.png

At some point the recursively processed point subset does only contain the start and end point of the dividing line. If this is case this line has to be a segment of the searched hull polygon and the recursion can come to an end.

 

Practical use

Everything seen so far is quite theoretical. You might ask which real world application does need something like QuickHull. I want to demonstrate the practical use of convex hulls using an example quite similar the what I am currently doing with them.

The example will cover Bézier curves. Bézier curves are used in computer graphics to mathematically define and draw curve segments. It is not that important to understand a Bézier curve in detail. What is however relevant is the fact that such a curve is defined using an arbitrary amount of control points. These control points affect the way the curve is shaped. You can imagine these points to be small centers of gravity which pull the curve into their direction.

bezier1.png

A simple example of such a curve is illustrated in the picture to the left. It consists of 4 control points. The first and last control point are always the start and end points of the curve. Every control point in between does not need to be on the resulting curve. They only affect the curve in some way.

The application I wrote the QuickHull implementation for needed to do some sort of visibility checking for these curves. I needed to know which curves weren't visible and therefore would not need to be drawn.

bezier2.png

At this point convex hulls come into account. Bézier curves have a nice feature. They are mathematically proven always surrounded by the convex hull of their control points. Therefore, the fact that the convex hull is not visible implies the curve is not visible. This check can be done a lot faster than calculating intersections with the real curve.

There are other real world applications of convex hulls like for example linear programming, as well.

 

Implementation in PHP

As I mentioned before, I implemented this algorithm in PHP. Apart from some vector math, the implementation is quite straight forward. It is a single PHP file containing a well documented class, encapsulating all the needed functionality. An array of points needs to be provided as input and the convex hull polygon points, in clockwise order, are outputted after the calculation has been done.

Download