Find the convex hull of a set of points using the Graham scan algorithm. The algorithm works as follows: 1. Find the bottom-most point (or left-most in case of tie) 2. Sort all other points by polar angle with respect to the bottom-most point 3. Process points in order, maintai
(points: Sequence[Point])
| 111 | |
| 112 | |
| 113 | def graham_scan(points: Sequence[Point]) -> list[Point]: |
| 114 | """ |
| 115 | Find the convex hull of a set of points using the Graham scan algorithm. |
| 116 | |
| 117 | The algorithm works as follows: |
| 118 | 1. Find the bottom-most point (or left-most in case of tie) |
| 119 | 2. Sort all other points by polar angle with respect to the bottom-most point |
| 120 | 3. Process points in order, maintaining a stack of hull candidates |
| 121 | 4. Remove points that would create a clockwise turn |
| 122 | |
| 123 | Args: |
| 124 | points: A sequence of Point objects |
| 125 | |
| 126 | Returns: |
| 127 | A list of Point objects representing the convex hull in counter-clockwise order. |
| 128 | Returns an empty list if there are fewer than 3 distinct points or if all |
| 129 | points are collinear. |
| 130 | |
| 131 | Time Complexity: O(n log n) due to sorting |
| 132 | Space Complexity: O(n) for the output hull |
| 133 | |
| 134 | >>> graham_scan([]) |
| 135 | [] |
| 136 | >>> graham_scan([Point(0, 0)]) |
| 137 | [] |
| 138 | >>> graham_scan([Point(0, 0), Point(1, 1)]) |
| 139 | [] |
| 140 | >>> hull = graham_scan([Point(0, 0), Point(1, 0), Point(0.5, 1)]) |
| 141 | >>> len(hull) |
| 142 | 3 |
| 143 | >>> Point(0, 0) in hull and Point(1, 0) in hull and Point(0.5, 1) in hull |
| 144 | True |
| 145 | """ |
| 146 | if len(points) <= 2: |
| 147 | return [] |
| 148 | |
| 149 | # Find the bottom-most point (left-most in case of tie) |
| 150 | min_point = min(points) |
| 151 | |
| 152 | # Remove the min_point from the list |
| 153 | points_list = [p for p in points if p != min_point] |
| 154 | if not points_list: |
| 155 | # Edge case where all points are the same |
| 156 | return [] |
| 157 | |
| 158 | def polar_angle_key(point: Point) -> tuple[float, float, float]: |
| 159 | """ |
| 160 | Key function for sorting points by polar angle relative to min_point. |
| 161 | |
| 162 | Points are sorted counter-clockwise. When two points have the same angle, |
| 163 | the farther point comes first (we'll remove duplicates later). |
| 164 | """ |
| 165 | # We use a dummy third point (min_point itself) to calculate relative angles |
| 166 | # Instead, we'll compute the angle between points |
| 167 | dx = point.x - min_point.x |
| 168 | dy = point.y - min_point.y |
| 169 | |
| 170 | # Use atan2 for angle, but we can also use cross product for comparison |