Blog post: https://lvngd.com/blog/convex-hull-graham-scan-algorithm-python/

convex_hull.py

import random

"""
Computes the Convex Hull with the Graham Scan algorithm

Use:
	h = ConvexHull()
	print(h.hull)
"""

class ConvexHull:
	def __init__(self, points):
		if not points:
			self.points = [(random.randint(0,100),random.randint(0,100)) for i in range(50)]
		else:
			self.points = points
		self.hull = self.compute_convex_hull()
    
	def get_cross_product(self,p1, p2, p3):
		return ((p2[0] - p1[0])*(p3[1] - p1[1])) - ((p2[1] - p1[1])*(p3[0] - p1[0]))

	def get_slope(self,p1, p2):
		if p1[0] == p2[0]:
			return float('inf')
		else:
			return 1.0*(p1[1]-p2[1])/(p1[0]-p2[0])

	def compute_convex_hull(self):
		hull = []
		self.points.sort(key=lambda x:[x[0],x[1]])
		start = self.points.pop(0)
		hull.append(start)
		self.points.sort(key=lambda p: (self.get_slope(p,start), -p[1],p[0]))
		for pt in self.points:
			hull.append(pt)
			while len(hull) > 2 and self.get_cross_product(hull[-3],hull[-2],hull[-1]) < 0:
				hull.pop(-2)
		return hull

convex_hull_fun.py

def orientation(p, q, r):
    return (q[0] - p[0]) * (r[1] - p[1]) - (r[0] - p[0]) * (q[1] - p[1])
    
def graham_scan(arr):
    stack = [arr[0], arr[1]]
    for a in arr[2:]:
        while len(stack) >= 2 and orientation(a, stack[-1], stack[-2]) <= 0:
            stack.pop()
        stack.append(a)
    stack.pop()
    return stack
    
def hull_method(pointlist):
    if len(pointlist) < 3:
        return []
    arr = sorted(pointlist)
    return graham_scan(arr) + graham_scan(arr[::-1])