Calculate a convex hull - The QuickHull algorithm
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.
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.
As you can see the convex hull in two dimensional space is the minimal polygon, which encloses all of the given points.
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.
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
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.
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
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.
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.
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.
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.
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.
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.
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.