Day 28: Convex hull
Published in
2 min readApr 21, 2017
Convex hull is a way to capture a set of points using another set of points that is preferable. In this case a continuous set that is convex and minimal, since convex and minimal is a property that’s always good to have.
There are many algorithms to find convex hull, but I like particularly this one.
Choose left-most point U and right-most point V. Both U and V reside on hull and UV forms a line that splits the set. On each side of UV choose the furthest point P, throw away all points inside triangle UVP and proceed recursively on UP and VP.
https://github.com/coells/100days
algorithm
def split(u, v, points):
# return points on left side of UV
return [p for p in points if np.cross(p - u, v - u) < 0]def extend(u, v, points):
if not points:
return [] # find furthest point W, and split search to WV, UW
w = min(points, key=lambda p: np.cross(p - u, v - u))
p1, p2 = split(w, v, points), split(u, w, points)
return extend(w, v, p1) + [w] + extend(u, w, p2)def convex_hull(points):
# find two hull points, U, V, and split to left and right search
u = min(points, key=lambda p: p[0])
v = max(points, key=lambda p: p[0])
left, right = split(u, v, points), split(v, u, points)
# find convex hull on each side
return [v] + extend(u, v, left) + \
[u] + extend(v, u, right) + [v]
run
> points = np.random.rand(100, 2)
> np.array(convex_hull(points))array([[ 9.95456010e-01, 7.65907653e-01],
[ 9.64101937e-01, 9.47636262e-01],
[ 7.49840951e-01, 9.68180575e-01],
[ 2.13580026e-01, 9.91177434e-01],
[ 1.18181500e-01, 9.56758533e-01],
[ 3.77237324e-02, 8.81109123e-01],
[ 2.75085295e-02, 2.27043559e-01],
[ 5.72172004e-02, 2.45227737e-02],
[ 4.40115492e-01, 5.46663495e-06],
[ 7.37937895e-01, 6.71680586e-02],
[ 8.47805083e-01, 9.26355385e-02],
[ 8.97086651e-01, 1.21673019e-01],
[ 9.57764617e-01, 1.98416655e-01],
[ 9.95456010e-01, 7.65907653e-01]])
