2 min read
The convex hull of a set of points is defined as the smallest convex polygon. I don’t think it’s wise to bring out convex hull problem in a programmmer interview, but it is a interesting problem involved some brilliant solutions.
Graham Scan is a really brilliant and straight forward way to find a convex hull of a set of points. I’ll take the following problem for example.
There are some trees, where each tree is represented by (x,y) coordinate in a two-dimensional garden. Your job is to fence the entire garden using the minimum length of rope as it is expensive. The garden is well fenced only if all the trees are enclosed. Your task is to help find the coordinates of trees which are exactly located on the fence perimeter. Example Input: [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]] Output: [[1,1],[2,0],[4,2],[3,3],[2,4]]
"""
Definition for a point.
class Point:
def __init__(self, a=0, b=0):
self.x = a
self.y = b
"""
class Solution:
"""
@param points: List[point]
@return: return List[point]
"""
def outerTrees(self, points):
# Computes the cross product of vectors p1p2 and p2p3
# value of 0 means points are colinear; < 0, cw; > 0, ccw
def cross(p1,p2,p3):
return (p2.x - p1.x)*(p3.y-p1.y) - (p2.y - p1.y)*(p3.x - p1.x)
# Computes slope of line between p1 and p2
def slope(p1, p2):
return 1.0*(p1.y-p2.y)/(p1.x-p2.x) if p1.x != p2.x else float('inf')
# Find the smallest left point and remove it from points
start = min(points, key = lambda p:(p.x,p.y))
points.pop(points.index(start))
# Sort points so that traversal is from start in a ccw circle.
points.sort(key= lambda p:(slope(p, start), -p.y, p.x))
# Add each point to the convex hull.
# If the last 3 points make a cw turn, the second to last point is wrong.
ans = [start]
for p in points:
ans.append(p)
while len(ans) > 2 and cross(ans[-3],ans[-2],ans[-1]) < 0:
ans.pop(-2)
return sorted(ans,key = lambda p:(p.x,p.y))