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
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