QuickHull

QuickHull is an algorithm for computing the convex hull of any finite set of points in two - or three-dimensional space. The convex hull of a set of points is described by a closed polygon that represents the connection of all extreme points of the set, and so includes all points of the set. An intuitive explanation of this commonly used shell is a rubber band that is stretched to the point set. This makes if it be taut on all outer points, the convex hull of the point set.

Naming and development

The name QuickHull derives from the similarity to Quicksort from, an algorithm for sorting arbitrary quantities. He finds for the first time mentioned in the book Computational geometry by Franco Preparata and Michael Shamos, in which the two authors present the algorithm described here, which takes up the ideas of other authors.

The basic idea

The algorithmic idea to QuickHull comes from the principle of " divide and rule ", which is often used in computer science. It describes the procedure to divide the problem into several smaller problems and solving them recursively applying the same algorithm. In this context, it is often tempted to choose the partition so skillfully that through this already fall out a large number of invalid volumes of solution. Through this kind of construction algorithms that have been designed according to this principle can often be implemented simply and clearly legible, since they have a intelligible recursive structure.

Example

The algorithm operates on an arbitrary finite set of points. There are no special requirements for the arrangement or number of points. However, a symmetrical arrangement of the points has a higher probability of the best-case (best case ) running time bound of leave and to be much slower.

To determine the initial allocation of the amount of the two extreme points of the X - axis are looking for. So those points which most left and most are right. These points can already be added to the polygon of the convex hull, since it guarantees its part are as extreme points.

The two points found form a straight line which divides the set of points into two parts. All points to the left of the line represent a lot and all points to the right of the straight the other. Right and left arise in this context, from the angle between the direction vector of the separation line and the vector defined by the start point of the line and the point to be checked. If this angle is less than 180 °, then the point is considered a right of the line, at angles greater than 180 ° than her left.

The two sets of points separated by this line are now processed recursively with the QuickHull algorithm further. In this example, only the left portion of the set of points is considered further. All statements made equivalent to take on the right part.

In the considered set of points that point is determined which has the maximum distance from the straight line. This is obviously also a part of this traverse. Together with the start and end points of the line creates a triangle.

The triangle is made up of three points, all of which are part of the convex -hull polygon. For this reason, all items can not be part of this polygon in the interior of this triangle, since they are already inside it. All points within this triangle can therefore be ignored in further recursive calls of the algorithm.

The resulting as sides of the triangle lines will now be considered as renewed separation line of the point set. All points to the left of the triangle represent a lot, all right points of the triangle the other.

This recursive layout and provision of other points is repeated until only the start and end points of the separation lines are still part of the set of points to be considered, because in this case it is clear that this is precisely one segment of this polygon.