Convex Hull
In short: the convex hull of a set of points is the smallest convex polygon that contains every one of them — stretch a rubber band around the points and let go, and it snaps to the hull. Andrew's monotone chain builds it in O(n log n): sort the points once by (x, y), then build two chains — a lower hull scanning left to right and an upper hull scanning right to left. Each chain is a stack: a new point is pushed on, but first, while the top of the stack and the new point do NOT make a left turn, the top point is popped — it would create a dent, so it can't be on the hull. Every point gets pushed once and popped at most once, so the whole walk after sorting is O(n).
Wrapping a boundary around five stops
Five of Meridian's stops sit at (0,0), (1,-1), (2,0), (3,-1) and
(4,0) — already sorted by x. Building the lower hull:
A new point is pushed, but first the stack pops any point that would make a non-left turn with it — a point that would dent the boundary inward never belongs on the hull.
Nothing to compare yet, so (0,0) just goes on. Stack, 1 item. Top is (0,0).
(2, 0) goes on the stack and comes right back off two points later —
pushed once, popped once, never visited again. That's why the whole scan,
after the one O(n log n) sort, costs O(n): the total number of pops across
the entire run can never exceed the total number of pushes.
One hull, two halves
The lower hull alone only bounds the bottom of the point set. Run the exact same pop-on-non-left-turn rule on the points in reverse, and you trace the top:
The square's four corners come back; (2,2), (1,3) and (3,1) are all
inside the square, so none of them survives either half's pops. Dropping
lower[-1] and upper[-1] matters because each half's LAST point is the
other half's FIRST point — joined without trimming, the hull would list
two of its four corners twice.
sorted(set(points)) works above because stops is written as real Python
tuples, and tuples are hashable. A point arriving from outside your code —
from a test, a form, a file — usually arrives as an [x, y] list
instead, and set() rejects a list outright: lists are mutable, so Python
won't let them sit inside a set or be a dict key. Convert each point to a
tuple first — sorted({tuple(p) for p in points}) — and it works
regardless of which one arrives.
Quick practice
def orientation(a, b, c):
cross = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
if cross > 0:
return 1
if cross < 0:
return -1
return 0
hull = [(0, 0), (1, -1)]
p = (2, 0)
print(len(hull) >= 2 and orientation(hull[-2], hull[-1], p) <= 0)def orientation(a, b, c):
cross = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
if cross > 0:
return 1
if cross < 0:
return -1
return 0
def half_hull(points):
hull = []
for p in points:
while len(hull) >= 2 and orientation(hull[-2], hull[-1], p) <= 0:
hull.pop()
hull.append(p)
return hull
print(half_hull([(0, 0), (1, 1), (2, 2), (3, 0)]))🎯 Your turn
Build convex_hull(points): return the convex hull's vertices,
counter-clockwise, with duplicates removed and no point repeated at the end.
convex_hull([(0,0), (4,0), (4,4), (0,4), (2,2)])→[(0,0), (4,0), (4,4), (0,4)]convex_hull([(0,0), (1,0), (2,0), (3,0)])→[(0,0), (3,0)]
Hint: points arrives as plain [x, y] lists, and a list can't go
inside a set() — it isn't hashable. Dedupe with
pts = sorted({tuple(p) for p in points}) instead. Build lower scanning
pts left to right and upper scanning reversed(pts), popping on
orientation(...) <= 0 each time. Return lower[:-1] + upper[:-1] (for 3+
points), converting each point back to a list before returning.
Press ▶ Run, try the Live App chips, then ✓ Check.