Graham's scan convex hull algorithm, updated for Python 3.x

graham_hull.py

def convex_hull_graham(points):
    '''
    Returns points on convex hull in CCW order according to Graham's scan algorithm. 
    By Tom Switzer <thomas.switzer@gmail.com>.
    '''
    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

Awesome. Is it possible to adjust it for tolerance?

Thank You!

I too faced this error :

return (a > b) - (a < b)
TypeError: numpy boolean subtract, the `-` operator, is not supported, use the bitwise_xor, the ^ operator, or the logical_xor function instead.

To fix this, I typecasted it to float :

def cmp(a, b):
        return float(a > b) - float(a < b)

Nice! Thanks.

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)