jarvis.py

# Jarvis March O(nh) - Tom Switzer <[email protected]>

TURN_LEFT, TURN_RIGHT, TURN_NONE = (1, -1, 0)

def turn(p, q, r):
    """Returns -1, 0, 1 if p,q,r forms a right, straight, or left turn."""
    return cmp((q[0] - p[0])*(r[1] - p[1]) - (r[0] - p[0])*(q[1] - p[1]), 0)

def _dist(p, q):
    """Returns the squared Euclidean distance between p and q."""
    dx, dy = q[0] - p[0], q[1] - p[1]
    return dx * dx + dy * dy

def _next_hull_pt(points, p):
    """Returns the next point on the convex hull in CCW from p."""
    q = p
    for r in points:
        t = turn(p, q, r)
        if t == TURN_RIGHT or t == TURN_NONE and _dist(p, r) > _dist(p, q):
            q = r
    return q

def convex_hull(points):
    """Returns the points on the convex hull of points in CCW order."""
    hull = [min(points)]
    for p in hull:
        q = _next_hull_pt(points, p)
        if q != hull[0]:
            hull.append(q)
    return hull

I think it is unnecessary to continue the loop after

q == hull[0].

whats the math behind the turn function?...is it calculating the area between the points to determine if its left or right?

its the determinant of the line that makes the hull with the target point?

casio101: imagine the cross product of the two vectors pq and qr extended to 3d space (some constant, e.g. 0, as third component). According to the right hand rule, the resulting z component of the cross product will be negative, if pq and qr are performing a right turn, zero if they are straight and positive if they perform a left turn.

To connect this to your remark about the area: only the absolute value of the resulting z component (or if z wouldn't be constant in the 3d extension: the resulting vector length) would be the area, not the raw value how you can see it in this code.

mgla - it doesn't continue, when it doesn't equal, you aren't adding any more values so the loop ends