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

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