Convex hull
- Algorithms course
- Expert
- Lesson 20/41
- 4 min
Compute the convex hull.
Convex hull
The convex hull of a point set is the smallest convex polygon that contains all points. Imagine stretching a rubber band around the points.
A common algorithm is Andrew's monotone chain: sort points by x, then build lower and upper hulls separately.
At each step we use the cross product to pop points that cause a right turn. Complexity is O(n log n).
Monotone chain
In Andrew's method we first sort points by x (then by y on ties). Then we build the lower hull left to right and the upper hull right to left.
While adding a new point to the lower hull, if the last three points make a right turn or are colinear we pop the middle one. This is tested with the cross product.
Finally, since the lower and upper hulls share endpoints, we drop one element from each and concatenate.
Practice convex_hull function
Write convex_hull(points). Return the convex hull of the point list in counterclockwise order. Print [(0, 0), (4, 0), (4, 3), (0, 3)] with print(convex_hull([(0,0), (4,0), (4,3), (0,3), (2,1)])).
Starter code
def convex_hull(points):
# Return the convex hullSample solution
def convex_hull(points):
# Return the convex hull
pts = sorted(set(points))
if len(pts) <= 1:
return pts
def cross(o, a, b):
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
lower = []
for p in pts:
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop()
lower.append(p)
upper = []
for p in reversed(pts):
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
upper.pop()
upper.append(p)
return lower[:-1] + upper[:-1]
print(convex_hull([(0,0), (4,0), (4,3), (0,3), (2,1)]))Expected output
[(0, 0), (4, 0), (4, 3), (0, 3)]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 hull pop
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= ____:
lower.pop()while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop()Explanation: With 0, right turn or colinear points are popped.
2 What is the complexity of Andrew's method?
pts = sorted(set(points))- O(n log n) Correct answer
- O(n)
- O(n²)
- O(2ⁿ)
Explanation: Sorting is O(n log n), scan is O(n); total O(n log n).
3 Convex hull concepts
| Term | Meaning |
|---|---|
monotone chain |
Andrew's method |
O(n log n) |
Complexity |
right turn |
Pop from hull |
sorting |
First step |