Constructs the convex hull of a set of 2D points using the melkman algorithm. The algorithm works by iteratively inserting points of a simple polygonal chain (meaning that no line segments between two consecutive points cross each other). Sorting the points yields such a polygonal c
(points: list[Point])
| 407 | |
| 408 | |
| 409 | def convex_hull_melkman(points: list[Point]) -> list[Point]: |
| 410 | """ |
| 411 | Constructs the convex hull of a set of 2D points using the melkman algorithm. |
| 412 | The algorithm works by iteratively inserting points of a simple polygonal chain |
| 413 | (meaning that no line segments between two consecutive points cross each other). |
| 414 | Sorting the points yields such a polygonal chain. |
| 415 | |
| 416 | For a detailed description, see http://cgm.cs.mcgill.ca/~athens/cs601/Melkman.html |
| 417 | |
| 418 | Runtime: O(n log n) - O(n) if points are already sorted in the input |
| 419 | |
| 420 | Parameters |
| 421 | --------- |
| 422 | points: array-like of object of Points, lists or tuples. |
| 423 | The set of 2d points for which the convex-hull is needed |
| 424 | |
| 425 | Returns |
| 426 | ------ |
| 427 | convex_set: list, the convex-hull of points sorted in non-decreasing order. |
| 428 | |
| 429 | See Also |
| 430 | -------- |
| 431 | |
| 432 | Examples |
| 433 | --------- |
| 434 | >>> convex_hull_melkman([[0, 0], [1, 0], [10, 1]]) |
| 435 | [(0.0, 0.0), (1.0, 0.0), (10.0, 1.0)] |
| 436 | >>> convex_hull_melkman([[0, 0], [1, 0], [10, 0]]) |
| 437 | [(0.0, 0.0), (10.0, 0.0)] |
| 438 | >>> convex_hull_melkman([[-1, 1],[-1, -1], [0, 0], [0.5, 0.5], [1, -1], [1, 1], |
| 439 | ... [-0.75, 1]]) |
| 440 | [(-1.0, -1.0), (-1.0, 1.0), (1.0, -1.0), (1.0, 1.0)] |
| 441 | >>> convex_hull_melkman([(0, 3), (2, 2), (1, 1), (2, 1), (3, 0), (0, 0), (3, 3), |
| 442 | ... (2, -1), (2, -4), (1, -3)]) |
| 443 | [(0.0, 0.0), (0.0, 3.0), (1.0, -3.0), (2.0, -4.0), (3.0, 0.0), (3.0, 3.0)] |
| 444 | """ |
| 445 | points = sorted(_validate_input(points)) |
| 446 | n = len(points) |
| 447 | |
| 448 | convex_hull = points[:2] |
| 449 | for i in range(2, n): |
| 450 | det = _det(convex_hull[1], convex_hull[0], points[i]) |
| 451 | if det > 0: |
| 452 | convex_hull.insert(0, points[i]) |
| 453 | break |
| 454 | elif det < 0: |
| 455 | convex_hull.append(points[i]) |
| 456 | break |
| 457 | else: |
| 458 | convex_hull[1] = points[i] |
| 459 | i += 1 |
| 460 | |
| 461 | for j in range(i, n): |
| 462 | if ( |
| 463 | _det(convex_hull[0], convex_hull[-1], points[j]) > 0 |
| 464 | and _det(convex_hull[-1], convex_hull[0], points[1]) < 0 |
| 465 | ): |
| 466 | # The point lies within the convex hull |
no test coverage detected