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)]
(points: list[tuple[int, int]])
| 91 | |
| 92 | |
| 93 | def graham_scan(points: list[tuple[int, int]]) -> list[tuple[int, int]]: |
| 94 | """Pure implementation of graham scan algorithm in Python |
| 95 | |
| 96 | :param points: The unique points on coordinates. |
| 97 | :return: The points on convex hell. |
| 98 | |
| 99 | Examples: |
| 100 | >>> graham_scan([(9, 6), (3, 1), (0, 0), (5, 5), (5, 2), (7, 0), (3, 3), (1, 4)]) |
| 101 | [(0, 0), (7, 0), (9, 6), (5, 5), (1, 4)] |
| 102 | |
| 103 | >>> graham_scan([(0, 0), (1, 0), (1, 1), (0, 1)]) |
| 104 | [(0, 0), (1, 0), (1, 1), (0, 1)] |
| 105 | |
| 106 | >>> graham_scan([(0, 0), (1, 1), (2, 2), (3, 3), (-1, 2)]) |
| 107 | [(0, 0), (1, 1), (2, 2), (3, 3), (-1, 2)] |
| 108 | |
| 109 | >>> graham_scan([(-100, 20), (99, 3), (1, 10000001), (5133186, -25), (-66, -4)]) |
| 110 | [(5133186, -25), (1, 10000001), (-100, 20), (-66, -4)] |
| 111 | """ |
| 112 | |
| 113 | if len(points) <= 2: |
| 114 | # There is no convex hull |
| 115 | raise ValueError("graham_scan: argument must contain more than 3 points.") |
| 116 | if len(points) == 3: |
| 117 | return points |
| 118 | # find the lowest and the most left point |
| 119 | minidx = 0 |
| 120 | miny, minx = maxsize, maxsize |
| 121 | for i, point in enumerate(points): |
| 122 | x = point[0] |
| 123 | y = point[1] |
| 124 | if y < miny: |
| 125 | miny = y |
| 126 | minx = x |
| 127 | minidx = i |
| 128 | if y == miny and x < minx: |
| 129 | minx = x |
| 130 | minidx = i |
| 131 | |
| 132 | # remove the lowest and the most left point from points for preparing for sort |
| 133 | points.pop(minidx) |
| 134 | |
| 135 | sorted_points = sorted(points, key=lambda point: angle_comparer(point, minx, miny)) |
| 136 | # This insert actually costs complexity, |
| 137 | # and you should instead add (minx, miny) into stack later. |
| 138 | # I'm using insert just for easy understanding. |
| 139 | sorted_points.insert(0, (minx, miny)) |
| 140 | |
| 141 | stack: deque[tuple[int, int]] = deque() |
| 142 | stack.append(sorted_points[0]) |
| 143 | stack.append(sorted_points[1]) |
| 144 | stack.append(sorted_points[2]) |
| 145 | # The first 3 points lines are towards the left because we sort them by their angle |
| 146 | # from minx, miny. |
| 147 | current_direction = Direction.left |
| 148 | |
| 149 | for i in range(3, len(sorted_points)): |
| 150 | while True: |
nothing calls this directly
no test coverage detected