Given a group of points on a plane. The Convex Hull algorithm calculates the shape (made up from the points itself) containing all these points. It can also be used on a collection of points of different dimensions. This implementation however covers points on a plane. It essentially calculates the lines between points which together contain all points. In comparing different solutions to this problem we can describe each algorithm in terms of it's big-O time complexity.
There are multiple Convex Hull algorithms but this solution is called Quickhull, is comes from the work of both W. Eddy in 1977 and also separately A. Bykat in 1978, this algorithm has an expected time complexity of O(n log n), but it's worst-case time-complexity can be O(n^2) . With average conditions the algorithm has ok efficiency, but it's time-complexity can start to become more exponential in cases of high symmetry or where there are points lying on the circumference of a circle for example.
The quickhull algorithm works as follows:
- The algorithm takes an input of a collection of points. These points should be ordered on their x-coordinate value.
- We first find the two points A and B with the minimum(A) and the maximum(B) x-coordinates (as these will obviously be part of the hull).
- 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. The two points found before along with this one form a triangle.
- 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.
Our function will have the following defininition:
findHull(points: [CGPoint], p1: CGPoint, p2: CGPoint)
findHull(S1, A, B) findHull(S2, B, A)
What this function does is the following:
pointsis empty we return as there are no points to the right of our line to add to our hull.
- Draw a line from
- Find the point in
pointsthat is furthest away from this line. (
maxPointto the hull right after
- Draw a line (
- Draw a line (
p2. (These lines now form a triangle)
- All points within this triangle are of course not part of the hull and thus can be ignored. We check which points in
pointsare to the right of
line1these are grouped in an array
- All points that are to the right of
line2are grouped in an array
s2. Note that there are no points that are both to the right of
maxPointwouldn't be the point furthest away from our initial line between
- We call
findHull(_, _, _)again on our new groups of points to find more hull points.
findHull(s1, p1, maxPoint) findHull(s2, maxPoint, p2)
This eventually leaves us with an array of points describing the convex hull.
Written for the Swift Algorithm Club by Jaap Wijnen.