Convex Hull (Gift Wrapping)

Problem

Compute the convex hull of a list of distinct integer points with the gift-wrapping algorithm.

Return the hull vertices in counterclockwise order starting from the lowest-x, then lowest-y point, skipping collinear intermediate points. Zero or one input points are returned as-is.

Hint

Always choose the point that turns most clockwise; ties extend to the farthest collinear point.

Test cases

case 1

in: [[[2,0],[0,0],[2,2],[0,2],[1,1]]]

expected: [[0,0],[2,0],[2,2],[0,2]]

case 2

in: [[[0,0],[4,0],[2,3],[2,1]]]

expected: [[0,0],[4,0],[2,3]]

case 3

in: [[[1,2]]]

expected: [[1,2]]

case 4

in: [[[0,0],[1,0],[2,0],[2,2],[0,2]]]

expected: [[0,0],[2,0],[2,2],[0,2]]

Starter codePython

def convex_hull(points):
    # Your code here
    pass

4 test cases · run your code against them in the editor