#!/usr/bin/python3 # positive if p,q,r is counterclockwise # negative if p,q,r is clockwise def orientation(p,q,r): return ((q[0]-p[0]) * (r[1]-p[1])) - ((r[0]-p[0]) * (q[1]-p[1])) def upperHull(P): P.sort() # Sort by x coordinate ch = [P[0]] for p in P[1:]: while len(ch) >= 2 and orientation(p, ch[-1], ch[-2]) < 0: ch.pop() # Remove a point from the upper hull ch.append(p) # Add a point to the upper hull return ch def lowerHull(P): P2 = [(-p[0], -p[1]) for p in P] # Turn 180 degrees ch = upperHull(P2) return [(-p[0], -p[1]) for p in ch] # Undo the turn of 180 degrees def convexHull(P): upper = upperHull(P) print("upper = ", upper) lower = lowerHull(P) print("lower = ", lower) return upper[0:-1] + lower[0:-1] # Concatenate upper and lower hulls P = [(0,3),(4,7),(2,9),(1,5),(3,2),(10,8),(4,2),(15,8),(3,5)] print("P = ", P) ch = convexHull(P) print("ch = ", ch)