Quickhull

<h2 id="algorithm">Algorithm</h2>

The 2-dimensional algorithm can be broken down into the following steps:<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

<ol><li>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 the ones with the minimum/maximum y, respectively.</li>
<li>Use the line formed by the two points to divide the set into two subsets of points, which will be processed recursively. We next describe how to determine the part of the hull above the line; the part of the hull below the line can be determined similarly.</li>
<li>Determine the point above the line with the maximum distance from the line. This point forms a triangle with the two points on the line.</li>
<li>The points lying inside of that triangle cannot be part of the convex hull and can therefore be ignored in the next steps.</li>
<li>Recursively repeat the previous two steps on the two lines formed by the two new sides of the triangle.</li>
<li>Continue until no more points are left, the recursion has come to an end and the points selected constitute the convex hull.</li></ol>

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:<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

<ol><li>Pick d + 1 points from the set that do not share a plane or a hyperplane. This forms an initial hull with facets Fs[].</li>
<li>For each F in Fs[], find all unassigned points that are "above" it; i.e., pointing away from the center of the hull, and assign them to an "outside" set F.O associated with F. The algorithm maintains the invariant that every point that has not been added to the hull but could potentially be a vertex of it is assigned to exactly one outside set.</li>
<li>For each F with a non-empty F.O:
<ol><li>Find the point p in F.O with the maximum distance from F and add it to the hull. Note that p will not necessarily be a vertex of the final hull, as it might be removed later.</li>
<li>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.</li>
<li>The boundary of V then forms the set of horizon ridges H.</li>
<li>Let Fnew[] be the set of facets created from p and all ridges in H.</li>
<li>Unassign all points in the outside sets of facets in V. For each new facet in Fnew[], perform step (2) only considering these newly unassigned points to initialize its outside set. Note that every point that remains unassigned at the end of this process lies within the current hull.</li>
<li>Delete the now-internal facets in V from Fs[]. Add the new facets in Fnew[] to Fs[] and continue the iteration.</li></ol></li></ol>
<h2 id="pseudocode-for-2d-set-of-points">Pseudocode for 2D set of points</h2>
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.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Convex_hull_algorithms/Wr70A2AI">Convex hull algorithms</a></li></ul>

<ul><li>Dave Mount. <a href="https://web.archive.org/web/20010411073422/http://www.cs.wustl.edu/~pless/506/l3.html">"Lecture 3: More Convex Hull Algorithms"</a>. Archived from <a href="http://www.cs.wustl.edu/~pless/506/l3.html">the original</a> on 11 April 2001.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="http://media.steampowered.com/apps/valve/2014/DirkGregorius_ImplementingQuickHull.pdf">Implementing QuickHull (GDC 2014)</a> – Algorithm presentation with 3D implementation details.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">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. <a href="http://www.cs.princeton.edu/~dpd/Papers/BarberDobkinHuhdanpaa.pdf" target="_blank">http://www.cs.princeton.edu/~dpd/Papers/BarberDobkinHuhdanpaa.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">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. <a href="http://www.cs.princeton.edu/~dpd/Papers/BarberDobkinHuhdanpaa.pdf" target="_blank">http://www.cs.princeton.edu/~dpd/Papers/BarberDobkinHuhdanpaa.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Greenfield, Jonathan S. (1 April 1990). "A Proof for a QuickHull Algorithm". Electrical Engineering and Computer Science - Technical Reports. <a href="https://surface.syr.edu/eecs_techreports/65" target="_blank">https://surface.syr.edu/eecs_techreports/65</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">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. <a href="http://www.cs.princeton.edu/~dpd/Papers/BarberDobkinHuhdanpaa.pdf" target="_blank">http://www.cs.princeton.edu/~dpd/Papers/BarberDobkinHuhdanpaa.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Greenfield, Jonathan S. (1 April 1990). "A Proof for a QuickHull Algorithm". Electrical Engineering and Computer Science - Technical Reports. <a href="https://surface.syr.edu/eecs_techreports/65" target="_blank">https://surface.syr.edu/eecs_techreports/65</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">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. <a href="http://www.cs.princeton.edu/~dpd/Papers/BarberDobkinHuhdanpaa.pdf" target="_blank">http://www.cs.princeton.edu/~dpd/Papers/BarberDobkinHuhdanpaa.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Smith, Jordan. "QuickHull 3D". algolist.ru. Retrieved 22 October 2019. <a href="https://algolist.ru/maths/geom/convhull/qhull3d.html" target="_blank">https://algolist.ru/maths/geom/convhull/qhull3d.html</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
</ol>

Quickhull open-in-new

Quickhull