Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Second solution in Uncategorized category for Convex Hull by Moff
from collections import namedtuple
from cmath import phase
class Point(namedtuple('Point', 'key x y')):
@property
def complex(self):
return self.x + 1j * self.y
def angle_to(self, other):
return phase(other.complex - self.complex)
def dist_to(self, other):
return abs(other.complex - self.complex)
def ccw(a, b, c):
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
def checkio(points):
points = [Point(i, x, y) for i, (x, y) in enumerate(points)]
hull = []
# sort by x coordinate
points.sort(key=lambda z: (z.x, z.y))
p0 = points.pop(0)
hull.append(p0)
# sort by polar angle with respect to base point
points.sort(key=lambda z: (p0.angle_to(z), -p0.dist_to(z)), reverse=True)
# find index of first point not collinear with points[0] and points[k1]
k = 0
while ccw(p0, points[k], points[k+1]) == 0:
hull.append(points[k]) # need to include border points
k += 1
hull.append(points[k])
# fixture sorting - need to include border points
points.sort(key=lambda z: (p0.angle_to(z), p0.dist_to(z)), reverse=True)
# Graham scan
for i in range(k+1, len(points)):
top = hull.pop()
while ccw(hull[-1], top, points[i]) > 0:
top = hull.pop()
hull.extend([top, points[i]])
return [x.key for x in hull]
Aug. 6, 2015
