Parameters --------- points: list or None, the hull of points from which to choose the next convex-hull point left: Point, the point to the left of line segment joining left and right right: The point to the right of the line segment joining left and right convex_s
(
points: list[Point], left: Point, right: Point, convex_set: set[Point]
)
| 363 | |
| 364 | |
| 365 | def _construct_hull( |
| 366 | points: list[Point], left: Point, right: Point, convex_set: set[Point] |
| 367 | ) -> None: |
| 368 | """ |
| 369 | |
| 370 | Parameters |
| 371 | --------- |
| 372 | points: list or None, the hull of points from which to choose the next convex-hull |
| 373 | point |
| 374 | left: Point, the point to the left of line segment joining left and right |
| 375 | right: The point to the right of the line segment joining left and right |
| 376 | convex_set: set, the current convex-hull. The state of convex-set gets updated by |
| 377 | this function |
| 378 | |
| 379 | Note |
| 380 | ---- |
| 381 | For the line segment 'ab', 'a' is on the left and 'b' on the right. |
| 382 | but the reverse is true for the line segment 'ba'. |
| 383 | |
| 384 | Returns |
| 385 | ------- |
| 386 | Nothing, only updates the state of convex-set |
| 387 | """ |
| 388 | if points: |
| 389 | extreme_point = None |
| 390 | extreme_point_distance = float("-inf") |
| 391 | candidate_points = [] |
| 392 | |
| 393 | for p in points: |
| 394 | det = _det(left, right, p) |
| 395 | |
| 396 | if det > 0: |
| 397 | candidate_points.append(p) |
| 398 | |
| 399 | if det > extreme_point_distance: |
| 400 | extreme_point_distance = det |
| 401 | extreme_point = p |
| 402 | |
| 403 | if extreme_point: |
| 404 | _construct_hull(candidate_points, left, extreme_point, convex_set) |
| 405 | convex_set.add(extreme_point) |
| 406 | _construct_hull(candidate_points, extreme_point, right, convex_set) |
| 407 | |
| 408 | |
| 409 | def convex_hull_melkman(points: list[Point]) -> list[Point]: |
no test coverage detected