**Input** = a set S of n points

Assume that there are at least 2 points in the input
set S of points

**QuickHull** (S)

{

// 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)

}

**FindHull** (Sk, P, Q)

{

// 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, S1are 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)

}

**Output** = convex hull

Back to the Applet Page

How to use this Applet