Algorithms
Convex hull
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.
Exercise 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)])).
Show example 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)]))
Test yourself
-
hull pop
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= ____:
lower.pop()
Show answer
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop()
-
What is the complexity of Andrew's method?
pts = sorted(set(points))
Show answer
O(n log n) — Sorting is O(n log n), scan is O(n); total O(n log n).
-
Convex hull concepts
- monotone chain
- Andrew's method
- O(n log n)
- Complexity
- right turn
- Pop from hull
- sorting
- First step
Next lesson: Line intersection
