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

It seems this code has some bugs. It does not remove colinear points.
For instance, If input is [[0, 0], [5, 3], [0, 5], [5, 3]] output should be [[0, 0], [0, 5], [5, 3]] but It returns [[0, 0], [0, 3], [0, 5], [5, 3]]

Hi, Thanks for commenting. I did leave in the collinear points - you can leave them in or remove them depending on your needs with the algorithm.

Broken?

If self.points = [(4,9),(4,8),(8,2),(6,2),(8,3),(5,4),(7,3)] , then hull = [(4, 9), (5, 4), (6, 2), (8, 2), (8, 3), (4, 8)]??

I used your code for a python script for Gimp, it works for me (I had to remove the duplicate points).
https://gist.github.com/JacquesDuflos/0a4914099d497631cff9211737e2f24f