Skip to content

Instantly share code, notes, and snippets.

Forked from tixxit/
Last active April 7, 2024 17:19
Show Gist options
  • Save arthur-e/5cf52962341310f438e96c1f3c3398b8 to your computer and use it in GitHub Desktop.
Save arthur-e/5cf52962341310f438e96c1f3c3398b8 to your computer and use it in GitHub Desktop.
Graham's scan convex hull algorithm, updated for Python 3.x
def convex_hull_graham(points):
Returns points on convex hull in CCW order according to Graham's scan algorithm.
By Tom Switzer <>.
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:
if not len(hull) or hull[-1] != 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
Copy link

Hey man, thank you very much!

Copy link

Thank you so much for posting this code, I've been banging my head against a brick wall all day trying to get scipy.spatial.ConvexHull to work, and this code worked perfectly first time!

Copy link

jxi24 commented Apr 2, 2019

I think I found a bug in your code. For certain sets of points, example given the points:
[[181, 864],
[182, 859],
[182, 860],
[182, 861],
[182, 862],
[182, 863],
[182, 864]]

The above algorithm finds the hull to just be [181, 864],[182, 864]]. This is obviously incorrect. If you change line 15 to be:
while len(hull) > 1 and turn(hull[-2], hull[-1], r) == TURN_RIGHT

The hull is given by: [[181, 864],[182, 859], [182, 864]].

This allows the hull to contain points that have no turns which occurs for topologies in which most of the points occur on a line with a few not on the line.

Copy link

I don't know but it was showing an error stating that subtraction was deprecated.
Hence, I changed part of code to this,

def cmp(a, b):
    return ((a>b).astype(np.float32) - (a<b).astype(np.float32)).astype(np.bool)

Copy link

samykbs commented Jun 23, 2020

great code, do you recommend some lectures to get more familiar with graham algorithm thanks

Copy link

Awesome. Is it possible to adjust it for tolerance?

Copy link

Thank You!

Copy link

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)

Copy link

Nice! Thanks.

Copy link

ferrine commented Oct 26, 2022

Numba version for the graham_hull

import numba
import numpy as np

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 reduce_keepleft(points):
    left = []
    for r in points:
        while len(left) > 1 and turn(left[-2], left[-1], r) != 1:
        if not len(left) or not np.allclose(left[-1], r, 1e-5, 1e-8, False):
    return left

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

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

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)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment