Quickhull
Quickhull is a method of computing the convex hull of a finite set of points in n-dimensional space. It uses a divide and conquer approach similar to that of quicksort, from which its name derives. Its worst case complexity for 2-dimensional and 3-dimensional space is considered to be , where is the number of input points and is the number of processed points[1]. However, unlike quicksort, there is no obvious way to convert quickhull into a randomized algorithm. Thus, its average time complexity cannot be easily calculated.
N-dimensional Quickhull was invented in 1996 by C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa.[1] It was an extension of Jonathan Scott Greenfield's 1990 planar Quickhull algorithm, although the 1996 authors did not know of his methods.[2] Instead, Barber et al describes it as a deterministic variant of Clarkson and Shor's 1989 algorithm.[1]
![](../I/m/Animation_depicting_the_quickhull_algorithm.gif)
Algorithm
![](../I/m/Quickhull_example3.svg.png)
Under average circumstances the algorithm works quite well, but processing usually becomes slow in cases of high symmetry or points lying on the circumference of a circle. The algorithm can be broken down to the following steps:[2]
- Find the points with minimum and maximum x coordinates, as these will always be part of the convex hull. If many points with the same minimum/maximum x exist, use ones with minimum/maximum y correspondingly.
- Use the line formed by the two points to divide the set in two subsets of points, which will be processed recursively.
- Determine the point, on one side of the line, with the maximum distance from the line. This point forms a triangle with those of the line.
- The points lying inside of that triangle cannot be part of the convex hull and can therefore be ignored in the next steps.
- Repeat the previous two steps on the two lines formed by the triangle (not the initial line).
- Keep on doing so on until no more points are left, the recursion has come to an end and the points selected constitute the convex hull.
![](../I/m/Quickhull_example6.svg.png)
![](../I/m/Quickhull_example7.svg.png)
The problem is more complex in the higher-dimensional case, as the hull is built from many facets; the data structure needs to account for that and record the line/plane/hyperplane (ridge) shared by neighboring facets too. For d dimensions:[1]
- Pick d + 1 points from the set that do not share a plane or a hyperplane. This forms an initial hull with facets Fs[].
- For each F in Fs[], find all unassigned points that are "above" it, i.e. pointing away from the center of the hull, and add it to an "outside" set F.O associated with F.
- For each F with a non-empty F.O:
- Find the point p with the maximum distance from F. We will add it to the hull.
- Create a visible set V and initialize it to F. Extend V in all directions for neighboring facets Fv until no further facets are visible from p. Fv being visible from p means that p is above Fv
- The boundary of V then forms the set of horizon ridges H.
- Let Fnew[] be the set of facets created from p and all ridges in H.
- For each new facet in Fnew[], perform step (2) and initialize its own outside sets. This time look only from points that are outside of a facet in V using their outside sets V[i].O, since we have only expanded in that direction.
- Delete the now-internal facets in V from Fs[]. Add the new facets in Fnew[] to Fs[] and continue the iteration.
Pseudocode for 2D set of points
Input = a set S of n points Assume that there are at least 2 points in the input set S of points function QuickHull(S) is // Find convex hull from the set S of n points Convex Hull := {} Find left and right most points, say A & B, and add A & B to convex hull Segment AB divides the remaining (n − 2) points into 2 groups S1 and S2 where S1 are points in S that are on the right side of the oriented line from A to B, and S2 are points in S that are on the right side of the oriented line from B to A FindHull(S1, A, B) FindHull(S2, B, A) Output := Convex Hull end function function FindHull(Sk, P, Q) is // Find points on convex hull from the set Sk of points // that are on the right side of the oriented line from P to Q if Sk has no point then return From the given set of points in Sk, find farthest point, say C, from segment PQ Add point C to convex hull at the location between P and Q Three points P, Q, and C partition the remaining points of Sk into 3 subsets: S0, S1, and S2 where S0 are points inside triangle PCQ, S1 are points on the right side of the oriented line from P to C, and S2 are points on the right side of the oriented line from C to Q. FindHull(S1, P, C) FindHull(S2, C, Q) end function
A pseudocode specialized for the 3D case is available from Jordan Smith. It includes a similar "maximum point" strategy for choosing the starting hull. If these maximum points are degenerate, the whole point cloud is as well.[3]
See also
References
- Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu (1 December 1996). "The quickhull algorithm for convex hulls" (PDF). ACM Transactions on Mathematical Software. 22 (4): 469–483. doi:10.1145/235815.235821.
- Greenfield, Jonathan S. (1 April 1990). "A Proof for a QuickHull Algorithm". Electrical Engineering and Computer Science - Technical Reports.
- Smith, Jordan. "QuickHull 3D". algolist.ru. Retrieved 22 October 2019.
- Dave Mount. "Lecture 3: More Convex Hull Algorithms".
- Pseudocode, "http://www.cse.yorku.ca/~aaw/Hang/quick_hull/Algorithm.html".
External links
- Implementing QuickHull (GDC 2014) – Algorithm presentation with 3D implementation details.