Convex Hull

The Convex Hull of a set of points is the smallest convex polygon that contains the set of points; finding such a polygon is one of the primary questions in the field of computational geometry.

The algorithm presented here is the Gift Wrapping Algorithm , which is a slow yet intuitive way of computing the convex hull. The algorithm has three components, each performed sequentially

1. Find the topmost point in your set (with the highest Y-coordinate). This will be the starting point for our polygon
2. Now, considering all the lines that go from Point 1 to all the other points, choose the line that makes the smallest angle with the positive X-axis. We now have our first side of the polygon
3. At each step after, we consider the set of all lines that go from our new point to all other points. We choose the line which makes the smallest angle with the previous line (intuitively, this minimization envelopes our points in the polygon). We continue to do so until we reach our initial point, at which point we have a polygon.

def findConvexHull(points):
    points = []

    firstPoint = min(points,key=y-coordinate)
    points.append(firstPoint)

    x_axis = vector([1,0])
    secondPoint = min(points, \
                key=angle(point-firstPoint, x_axis))
    points.append(secondPoint)

    while points[-1] != firstPoint:
        lastPoint = points[-1]
        lastLine = points[-1] - points[-2]
        newPoint =  min(points, \
                key=angle(point-lastPoint, lastLine))
        points.append(newPoint)
    return points