graham_scan.py

"""
This is a pure Python implementation of the Graham scan algorithm
Source: https://en.wikipedia.org/wiki/Graham_scan

For doctests run following command:
python3 -m doctest -v graham_scan.py
"""

from __future__ importannotations

fromcollectionsimportdeque
fromenumimportEnum
frommathimportatan2, degrees
fromsysimportmaxsize


# traversal from the lowest and the most left point in anti-clockwise direction
# if direction gets right, the previous point is not the convex hull.
classDirection(Enum):
left=1
straight=2
right=3

def__repr__(self):
returnf"{self.__class__.__name__}.{self.name}"


defangle_comparer(point: tuple[int, int], minx: int, miny: int) ->float:
"""Return the angle toward to point from (minx, miny)

 :param point: The target point
 minx: The starting point's x
 miny: The starting point's y
 :return: the angle

 Examples:
 >>> angle_comparer((1,1), 0, 0)
 45.0

 >>> angle_comparer((100,1), 10, 10)
 -5.710593137499642

 >>> angle_comparer((5,5), 2, 3)
 33.690067525979785
 """
# sort the points accorgind to the angle from the lowest and the most left point
x, y=point
returndegrees(atan2(y-miny, x-minx))


defcheck_direction(
starting: tuple[int, int], via: tuple[int, int], target: tuple[int, int]
) ->Direction:
"""Return the direction toward to the line from via to target from starting

 :param starting: The starting point
 via: The via point
 target: The target point
 :return: the Direction

 Examples:
 >>> check_direction((1,1), (2,2), (3,3))
 Direction.straight

 >>> check_direction((60,1), (-50,199), (30,2))
 Direction.left

 >>> check_direction((0,0), (5,5), (10,0))
 Direction.right
 """
x0, y0=starting
x1, y1=via
x2, y2=target
via_angle=degrees(atan2(y1-y0, x1-x0))
via_angle%=360
target_angle=degrees(atan2(y2-y0, x2-x0))
target_angle%=360
# t-
# \ \
# \ v
# \|
# s
# via_angle is always lower than target_angle, if direction is left.
# If they are same, it means they are on a same line of convex hull.
iftarget_angle>via_angle:
returnDirection.left
eliftarget_angle==via_angle:
returnDirection.straight
else:
returnDirection.right


defgraham_scan(points: list[tuple[int, int]]) ->list[tuple[int, int]]:
"""Pure implementation of graham scan algorithm in Python

 :param points: The unique points on coordinates.
 :return: The points on convex hell.

 Examples:
 >>> graham_scan([(9, 6), (3, 1), (0, 0), (5, 5), (5, 2), (7, 0), (3, 3), (1, 4)])
 [(0, 0), (7, 0), (9, 6), (5, 5), (1, 4)]

 >>> graham_scan([(0, 0), (1, 0), (1, 1), (0, 1)])
 [(0, 0), (1, 0), (1, 1), (0, 1)]

 >>> graham_scan([(0, 0), (1, 1), (2, 2), (3, 3), (-1, 2)])
 [(0, 0), (1, 1), (2, 2), (3, 3), (-1, 2)]

 >>> graham_scan([(-100, 20), (99, 3), (1, 10000001), (5133186, -25), (-66, -4)])
 [(5133186, -25), (1, 10000001), (-100, 20), (-66, -4)]
 """

iflen(points) <=2:
# There is no convex hull
raiseValueError("graham_scan: argument must contain more than 3 points.")
iflen(points) ==3:
returnpoints
# find the lowest and the most left point
minidx=0
miny, minx=maxsize, maxsize
fori, pointinenumerate(points):
x=point[0]
y=point[1]
ify<miny:
miny=y
minx=x
minidx=i
ify==minyandx<minx:
minx=x
minidx=i

# remove the lowest and the most left point from points for preparing for sort
points.pop(minidx)

sorted_points=sorted(points, key=lambdapoint: angle_comparer(point, minx, miny))
# This insert actually costs complexity,
# and you should instead add (minx, miny) into stack later.
# I'm using insert just for easy understanding.
sorted_points.insert(0, (minx, miny))

stack: deque[tuple[int, int]] =deque()
stack.append(sorted_points[0])
stack.append(sorted_points[1])
stack.append(sorted_points[2])
# The first 3 points lines are towards the left because we sort them by their angle
# from minx, miny.
current_direction=Direction.left

foriinrange(3, len(sorted_points)):
whileTrue:
starting=stack[-2]
via=stack[-1]
target=sorted_points[i]
next_direction=check_direction(starting, via, target)

ifnext_direction==Direction.left:
current_direction=Direction.left
break
ifnext_direction==Direction.straight:
ifcurrent_direction==Direction.left:
# We keep current_direction as left.
# Because if the straight line keeps as straight,
# we want to know if this straight line is towards left.
break
elifcurrent_direction==Direction.right:
# If the straight line is towards right,
# every previous points on that straight line is not convex hull.
stack.pop()
ifnext_direction==Direction.right:
stack.pop()
stack.append(sorted_points[i])
returnlist(stack)