convexhull.py

#!/usr/bin/env python2

# make sure to install shapely and matplotlib
# pip install shapely matplotlib
# maybe use a virtual environment

p1=(350,75)
p2=(379,161)
p3=(469,161)
p4=(397,215)
p5=(423,301)
p6=(350,250)
p7=(277,301)
p8=(303,215)
p9=(231,161)
p10=(321,161)

points = [p1, p2, p3, p3, p5, p6, p7, p8, p9, p10]

def convex_hull(points):

    #sort points by x coordinate
    points = sorted(points, key=lambda point: point[0])

    # storage for upper and lower parts of hull
    upperHull = []
    lowerHull = []

    for point in points:
        #as long as there are at least 2 elements in the lower hull and
        # point is right to the directed ray from uh-2 to uh-1
        # remove the last point of the lower hull as it does not contribute to the hull
        while len(lowerHull) >= 2 and isLeftOf(lowerHull[-2], lowerHull[-1], point) <= 0:
            lowerHull.pop()
        lowerHull.append(point)

    points.reverse()

    for point in points:
        while len(upperHull) >= 2 and isLeftOf(upperHull[-2], upperHull[-1], point) <= 0:
            upperHull.pop()
        upperHull.append(point)

    return lowerHull[:-1] + upperHull[:-1]

# TODO maybe rename
def isLeftOf(start, end, point):
    (x1, y1) = start
    (x2, y2) = end
    (x3, y3) = point
    return (x2-x1)*(y3-y1)-(y2-y1)*(x3-x1)

def visualize(points, hull=None):
    GRAY = '#000080'
    from matplotlib import pyplot
    from shapely.geometry import LineString, MultiPoint
    figure = pyplot.figure(1, dpi=90)
    ax = figure.add_subplot(121)
    for x,y in points:
        ax.plot(x, y, 'o', color=GRAY, zorder=1)
    ax.set_title('convex hull')
    line = LineString(hull+[hull[0]])
    x, y = line.xy
    ax.plot(x, y, color='#ffcc33', linewidth=2, solid_capstyle='round', zorder=0)
    ax.set_aspect(1)
    pyplot.show()

visualize(points, convex_hull(points))