Instantly share code, notes, and snippets.

# arthur-e/graham_hull.py

Forked from tixxit/hull.py
Last active April 7, 2024 17:19
Show Gist options
• Save arthur-e/5cf52962341310f438e96c1f3c3398b8 to your computer and use it in GitHub Desktop.
Graham's scan convex hull algorithm, updated for Python 3.x
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 def convex_hull_graham(points): ''' Returns points on convex hull in CCW order according to Graham's scan algorithm. By Tom Switzer . ''' TURN_LEFT, TURN_RIGHT, TURN_NONE = (1, -1, 0) def cmp(a, b): return (a > b) - (a < b) def turn(p, q, r): return cmp((q[0] - p[0])*(r[1] - p[1]) - (r[0] - p[0])*(q[1] - p[1]), 0) def _keep_left(hull, r): while len(hull) > 1 and turn(hull[-2], hull[-1], r) != TURN_LEFT: hull.pop() if not len(hull) or hull[-1] != r: hull.append(r) return hull points = sorted(points) l = reduce(_keep_left, points, []) u = reduce(_keep_left, reversed(points), []) return l.extend(u[i] for i in range(1, len(u) - 1)) or l

Nice! Thanks.

### ferrine commented Oct 26, 2022 • edited

Numba version for the graham_hull

```import numba
import numpy as np

@numba.njit
def cmp(a, b):
return (a > b) - (a < b)

@numba.njit
def turn(p, q, r):
return cmp((q[..., 0] - p[..., 0])*(r[..., 1] - p[..., 1]) - (r[..., 0] - p[..., 0])*(q[..., 1] - p[..., 1]), 0)

@numba.njit
def reduce_keepleft(points):
left = []
for r in points:
while len(left) > 1 and turn(left[-2], left[-1], r) != 1:
left.pop()
if not len(left) or not np.allclose(left[-1], r, 1e-5, 1e-8, False):
left.append(r)
return left

@numba.njit
def sort(points):
for i in range(points.shape[-1]-1, -1, -1):
idx = np.argsort(points[:, i], kind="mergesort")
points = points[idx]
return points

@numba.njit
def stack(alist):
out = np.empty((len(alist), *alist[0].shape))
for i, r in enumerate(alist):
out[i] = r
return out

@numba.njit
def convex_hull_graham(points):
points = sort(points)
l = reduce_keepleft(points)
u = reduce_keepleft(points[::-1])
hull = l + u[1:-1]
return stack(hull)```