grahams san

grahams.py

#!/usr/bin/python
# -*- encoding: utf-8 -*-
# pylint: disable=invalid-name,missing-docstring,bad-builtin,star-args
from operator import itemgetter
from math import atan2
from functools import partial

def polar(x, origin):
    # atan2 range -> [-π, π]
    # return range -> [0, π] as our origin has the minimum y coordinate
    # CAUTION: based on the assumption that origin has the min-y-coordinate
    return atan2(x[1] - origin[1], x[0] - origin[0])

def ccw(a, b, c):
    """
                    1   | ax  ay  1 |
    area(a, b, c) = - * | bx  by  1 |
                    2   | cx  cy  1 |
    a vector calculus application,
        counter-clockwise turn positive area.
        colckwise turn negative area.
        collinear zero area.
    """
    return ((b[0] - a[0])*(c[1] - a[1]) - (b[1] - a[1])*(c[0] - a[0])) > 0

def grahams(points):
    """
    :points:
        [(x1, y1), (x2, y2), (x3, y3), ..., (xn, yn)]
    """
    n = len(points)
    start = min(points, key=itemgetter(1))
    points = sorted(points, key=partial(polar, origin=start))
    hull = []
    for x in xrange(n):
        while len(hull) >= 2 and not ccw(hull[-2], hull[-1], points[x]):
            hull.pop()
        hull.append(points[x])
    return hull


def main():
    from random import randrange
    points = [(randrange(20), randrange(10)) for _ in xrange(30)]
    hull = grahams(points)
    print 'original points'
    out = []
    for y in xrange(10, -1, -1):
        for x in xrange(20):
            out.append('*' if (x, y) in points else ' ')
        out.append('\n')
    print ''.join(out)
    print 'convex hull points'
    out = []
    for y in xrange(10, -1, -1):
        for x in xrange(20):
            out.append('*' if (x, y) in hull else ' ')
        out.append('\n')
    print ''.join(out)

main()