|
| 1 | +""" |
| 2 | +This is a pure Python implementation of the merge-insertion sort algorithm |
| 3 | +Source: https://en.wikipedia.org/wiki/Graham_scan |
| 4 | +
|
| 5 | +For doctests run following command: |
| 6 | +python3 -m doctest -v graham_scan.py |
| 7 | +""" |
| 8 | + |
| 9 | +from __future__ import annotations |
| 10 | + |
| 11 | +from collections import deque |
| 12 | +from enum import Enum |
| 13 | +from math import atan2, degrees |
| 14 | +from sys import maxsize |
| 15 | + |
| 16 | + |
| 17 | +def graham_scan(points: list[list[int, int]]) -> list[list[int, int]]: |
| 18 | + """Pure implementation of graham scan algorithm in Python |
| 19 | +
|
| 20 | + :param points: The unique points on coordinates. |
| 21 | + :return: The points on convex hell. |
| 22 | +
|
| 23 | + Examples: |
| 24 | + >>> graham_scan([(9, 6), (3, 1), (0, 0), (5, 5), (5, 2), (7, 0), (3, 3), (1, 4)]) |
| 25 | + [(0, 0), (7, 0), (9, 6), (5, 5), (1, 4)] |
| 26 | +
|
| 27 | + >>> graham_scan([(0, 0), (1, 0), (1, 1), (0, 1)]) |
| 28 | + [(0, 0), (1, 0), (1, 1), (0, 1)] |
| 29 | +
|
| 30 | + >>> graham_scan([(0, 0), (1, 1), (2, 2), (3, 3), (-1, 2)]) |
| 31 | + [(0, 0), (1, 1), (2, 2), (3, 3), (-1, 2)] |
| 32 | +
|
| 33 | + >>> graham_scan([(-100, 20), (99, 3), (1, 10000001), (5133186, -25), (-66, -4)]) |
| 34 | + [(5133186, -25), (1, 10000001), (-100, 20), (-66, -4)] |
| 35 | + """ |
| 36 | + |
| 37 | + if len(points) <= 2: |
| 38 | + # There is no convex hull |
| 39 | + raise ValueError("graham_scan: argument must contain more than 3 points.") |
| 40 | + if len(points) == 3: |
| 41 | + return points |
| 42 | + # find the lowest and the most left point |
| 43 | + minidx = 0 |
| 44 | + miny, minx = maxsize, maxsize |
| 45 | + for i, point in enumerate(points): |
| 46 | + x = point[0] |
| 47 | + y = point[1] |
| 48 | + if y < miny: |
| 49 | + miny = y |
| 50 | + minx = x |
| 51 | + minidx = i |
| 52 | + if y == miny: |
| 53 | + if x < minx: |
| 54 | + minx = x |
| 55 | + minidx = i |
| 56 | + |
| 57 | + # remove the lowest and the most left point from points for preparing for sort |
| 58 | + points.pop(minidx) |
| 59 | + |
| 60 | + def angle_comparer(point: list[int, int], minx: int, miny: int) -> float: |
| 61 | + """Return the angle toward to point from (minx, miny) |
| 62 | +
|
| 63 | + :param point: The target point |
| 64 | + minx: The starting point's x |
| 65 | + miny: The starting point's y |
| 66 | + :return: the angle |
| 67 | +
|
| 68 | + Examples: |
| 69 | + >>> angle_comparer([1,1], 0, 0) |
| 70 | + 45.0 |
| 71 | +
|
| 72 | + >>> angle_comparer([100,1], 10, 10) |
| 73 | + -5.710593137499642 |
| 74 | +
|
| 75 | + >>> angle_comparer([5,5], 2, 3) |
| 76 | + 33.690067525979785 |
| 77 | + """ |
| 78 | + # sort the points accorgind to the angle from the lowest and the most left point |
| 79 | + x = point[0] |
| 80 | + y = point[1] |
| 81 | + angle = degrees(atan2(y - miny, x - minx)) |
| 82 | + return angle |
| 83 | + |
| 84 | + sorted_points = sorted(points, key=lambda point: angle_comparer(point, minx, miny)) |
| 85 | + # This insert actually costs complexity, |
| 86 | + # and you should insteadly add (minx, miny) into stack later. |
| 87 | + # I'm using insert just for easy understanding. |
| 88 | + sorted_points.insert(0, (minx, miny)) |
| 89 | + |
| 90 | + # traversal from the lowest and the most left point in anti-clockwise direction |
| 91 | + # if direction gets right, the previous point is not the convex hull. |
| 92 | + class Direction(Enum): |
| 93 | + left = 1 |
| 94 | + straight = 2 |
| 95 | + right = 3 |
| 96 | + |
| 97 | + def check_direction( |
| 98 | + starting: list[int, int], via: list[int, int], target: list[int, int] |
| 99 | + ) -> Direction: |
| 100 | + """Return the direction toward to the line from via to target from starting |
| 101 | +
|
| 102 | + :param starting: The starting point |
| 103 | + via: The via point |
| 104 | + target: The target point |
| 105 | + :return: the Direction |
| 106 | +
|
| 107 | + Examples: |
| 108 | + >>> check_direction([1,1], [2,2], [3,3]) |
| 109 | + Direction.straight |
| 110 | +
|
| 111 | + >>> check_direction([60,1], [-50,199], [30,2]) |
| 112 | + Direction.left |
| 113 | +
|
| 114 | + >>> check_direction([0,0], [5,5], [10,0]) |
| 115 | + Direction.right |
| 116 | + """ |
| 117 | + x0, y0 = starting |
| 118 | + x1, y1 = via |
| 119 | + x2, y2 = target |
| 120 | + via_angle = degrees(atan2(y1 - y0, x1 - x0)) |
| 121 | + if via_angle < 0: |
| 122 | + via_angle += 360 |
| 123 | + target_angle = degrees(atan2(y2 - y0, x2 - x0)) |
| 124 | + if target_angle < 0: |
| 125 | + target_angle += 360 |
| 126 | + # t- |
| 127 | + # \ \ |
| 128 | + # \ v |
| 129 | + # \| |
| 130 | + # s |
| 131 | + # via_angle is always lower than target_angle, if direction is left. |
| 132 | + # If they are same, it means they are on a same line of convex hull. |
| 133 | + if target_angle > via_angle: |
| 134 | + return Direction.left |
| 135 | + if target_angle == via_angle: |
| 136 | + return Direction.straight |
| 137 | + if target_angle < via_angle: |
| 138 | + return Direction.right |
| 139 | + |
| 140 | + stack = deque() |
| 141 | + stack.append(sorted_points[0]) |
| 142 | + stack.append(sorted_points[1]) |
| 143 | + stack.append(sorted_points[2]) |
| 144 | + # In any ways, the first 3 points line are towards left. |
| 145 | + # Because we sort them the angle from minx, miny. |
| 146 | + current_direction = Direction.left |
| 147 | + |
| 148 | + for i in range(3, len(sorted_points)): |
| 149 | + while True: |
| 150 | + starting = stack[-2] |
| 151 | + via = stack[-1] |
| 152 | + target = sorted_points[i] |
| 153 | + next_direction = check_direction(starting, via, target) |
| 154 | + |
| 155 | + if next_direction == Direction.left: |
| 156 | + current_direction = Direction.left |
| 157 | + break |
| 158 | + if next_direction == Direction.straight: |
| 159 | + if current_direction == Direction.left: |
| 160 | + # We keep current_direction as left. |
| 161 | + # Because if the straight line keeps as straight, |
| 162 | + # we want to know if this straight line is towards left. |
| 163 | + break |
| 164 | + elif current_direction == Direction.right: |
| 165 | + # If the straight line is towards right, |
| 166 | + # every previous points on those straigh line is not convex hull. |
| 167 | + stack.pop() |
| 168 | + if next_direction == Direction.right: |
| 169 | + stack.pop() |
| 170 | + stack.append(sorted_points[i]) |
| 171 | + return list(stack) |
0 commit comments