Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Graham scan solution in Clear category for Convex Hull by bryukh
#Solution for checkio task
#http://www.checkio.org/mission/task/info/convex-hull/
#author: Bryukh
from math import acos, sqrt, hypot
def find_length(a, b):
"""list[int, int], list[int, int] -> float
Find length of vector ab.
>>> find_length([1, 1], [1, 3])
2.0
:param a,b list: coordinates of points.
:return float: Length of vector.
"""
return hypot(a[0] - b[0], a[1] - b[1])
def find_angle(a, b, c):
"""list[int, int], list[int, int], list[int, int] -> float
Find angle between vectors ab and ac.
Using law of cosines.
:param a,b,c list: coordinates of points.
:return float: Angle in radian.
"""
ab = find_length(a, b)
bc = find_length(b, c)
ac = find_length(a, c)
return round(acos((ab ** 2 + ac ** 2 - bc ** 2) / (2 * ab * ac)), 13)
def clockwise(a, b, c):
"""list[int, int], list[int, int], list[int, int] -> float
Find rotate direction from ab to bc.
:param a,b,c list: coordinates of points.
:return float: if negative -- right turn, 0 -- collinear, positive -- left.
"""
rotate = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
return rotate / abs(rotate) if rotate else 0
def checkio(points):
"""list[list[int, int]] -> list[int]
Find the convex hull.
Using Graham scan algorithm (little modified).
>>> checkio([[3, 8], [1, 6], [6, 2], [7, 6], [5, 5], [8, 4], [6, 8]])
[1, 0, 6, 3, 5, 2]
:param points list: List of points coordinates.
:return list: Indexes of points, which form convex hull in clockwise order.
"""
p0 = min(points)
result = [p0]
stack = [p[:] for p in points]
#not include start
stack.remove(p0)
#sort by angle from p0 and inverse Y-axis, if angle equal sort by distance
stack.sort(key=lambda x: [find_angle(p0, [p0[0], max(x[1], p0[1] + 1)], x),
-find_length(p0, x)],
reverse=True)
p1 = stack.pop()
result.append(p1)
p2 = stack.pop()
while True:
rotate = clockwise(p0, p1, p2)
if rotate > 0:
#exclude point from result and step back
result.pop()
p0, p1, p2 = result[-2], result[-1], p2
continue
if not rotate:
p1, p2 = sorted([p2, p1], key=lambda x: find_length(p0, x))
result[-1] = p1
result.append(p2)
p0, p1 = p1, p2
if not stack:
break
p2 = stack.pop()
return [points.index(p) for p in result]
May 2, 2013
