42 lines
1.2 KiB
Python
42 lines
1.2 KiB
Python
# Use atan2 instead of acos to calc angle; atan2(x,y) of the point we potentially want to add
|
|
from math import acos, sqrt
|
|
|
|
from profile import Profiler
|
|
from util import Vector, Point, gen_point
|
|
|
|
|
|
@Profiler("calculating angle")
|
|
def calc_angle(v1: Vector, v2: Vector) -> float:
|
|
dot = (v1.x * v2.x) + (v1.y * v2.y)
|
|
len_1 = sqrt(v1.x**2 + v1.y**2)
|
|
len_2 = sqrt(v2.x**2 + v2.y**2)
|
|
|
|
tmp = dot / (len_1 * len_2)
|
|
return acos(max(min(tmp, 1), -1)) # acos is only defined in [-1,1]
|
|
|
|
|
|
@Profiler("calculating vector")
|
|
def calc_vector(p1: Point, p2: Point) -> Vector:
|
|
return Vector((p2.x - p1.x), (p2. y - p1.y))
|
|
|
|
|
|
@Profiler("gift_wrapper")
|
|
def rapper(points: set):
|
|
min_pt = min(points)
|
|
hull = [min_pt]
|
|
comp_vec = Vector(0, 1)
|
|
with Profiler("iterating points", excluded=("calculating angle", "calculating vector")):
|
|
while True:
|
|
hull.append(min(points - {hull[-1]},
|
|
key=lambda p: calc_angle(comp_vec, calc_vector(hull[-1], p))))
|
|
|
|
comp_vec = calc_vector(hull[-2], hull[-1])
|
|
|
|
if hull[-1] == min_pt:
|
|
return hull
|
|
|
|
|
|
if __name__ == '__main__':
|
|
points = {gen_point() for _ in range(30)}
|
|
hull = rapper(points)
|