Code Coverage |
||||||||||
Lines |
Functions and Methods |
Classes and Traits |
||||||||
| Total | |
100.00% |
22 / 22 |
|
100.00% |
2 / 2 |
CRAP | |
100.00% |
1 / 1 |
| MonotoneChain | |
100.00% |
22 / 22 |
|
100.00% |
2 / 2 |
11 | |
100.00% |
1 / 1 |
| __construct | n/a |
0 / 0 |
n/a |
0 / 0 |
1 | |||||
| createConvexHull | |
100.00% |
21 / 21 |
|
100.00% |
1 / 1 |
8 | |||
| sort | |
100.00% |
1 / 1 |
|
100.00% |
1 / 1 |
2 | |||
| 1 | <?php |
| 2 | /** |
| 3 | * Jingga |
| 4 | * |
| 5 | * PHP Version 8.1 |
| 6 | * |
| 7 | * @package phpOMS\Math\Geometry\ConvexHull |
| 8 | * @copyright Dennis Eichhorn |
| 9 | * @license OMS License 2.0 |
| 10 | * @version 1.0.0 |
| 11 | * @link https://jingga.app |
| 12 | */ |
| 13 | declare(strict_types=1); |
| 14 | |
| 15 | namespace phpOMS\Math\Geometry\ConvexHull; |
| 16 | |
| 17 | /** |
| 18 | * Andrew's monotone chain convex hull algorithm class. |
| 19 | * |
| 20 | * @package phpOMS\Math\Geometry\ConvexHull |
| 21 | * @license OMS License 2.0 |
| 22 | * @link https://jingga.app |
| 23 | * @since 1.0.0 |
| 24 | */ |
| 25 | final class MonotoneChain |
| 26 | { |
| 27 | /** |
| 28 | * Constructor. |
| 29 | * |
| 30 | * @since 1.0.0 |
| 31 | * @codeCoverageIgnore |
| 32 | */ |
| 33 | private function __construct() |
| 34 | { |
| 35 | } |
| 36 | |
| 37 | /** |
| 38 | * Create convex hull |
| 39 | * |
| 40 | * @param array<int, array{x:int|float, y:int|float}> $points Points (Point Cloud) |
| 41 | * |
| 42 | * @return array<int, array{x:int|float, y:int|float}> |
| 43 | * |
| 44 | * @since 1.0.0 |
| 45 | */ |
| 46 | public static function createConvexHull(array $points) : array |
| 47 | { |
| 48 | if (($n = \count($points)) < 2) { |
| 49 | return $points; |
| 50 | } |
| 51 | |
| 52 | \uasort($points, [self::class, 'sort']); |
| 53 | |
| 54 | $k = 0; |
| 55 | $result = []; |
| 56 | |
| 57 | // Lower hull |
| 58 | for ($i = 0; $i < $n; ++$i) { |
| 59 | while ($k >= 2 |
| 60 | && ($result[$k - 1]['x'] - $result[$k - 2]['x']) * ($points[$i]['y'] - $result[$k - 2]['y']) |
| 61 | - ($result[$k - 1]['y'] - $result[$k - 2]['y']) * ($points[$i]['x'] - $result[$k - 2]['x'] |
| 62 | ) <= 0 |
| 63 | ) { |
| 64 | --$k; |
| 65 | } |
| 66 | |
| 67 | $result[$k++] = $points[$i]; |
| 68 | } |
| 69 | |
| 70 | // Upper hull |
| 71 | for ($i = $n - 2, $t = $k + 1; $i >= 0; --$i) { |
| 72 | while ($k >= $t |
| 73 | && ($result[$k - 1]['x'] - $result[$k - 2]['x']) * ($points[$i]['y'] - $result[$k - 2]['y']) |
| 74 | - ($result[$k - 1]['y'] - $result[$k - 2]['y']) * ($points[$i]['x'] - $result[$k - 2]['x'] |
| 75 | ) <= 0 |
| 76 | ) { |
| 77 | --$k; |
| 78 | } |
| 79 | |
| 80 | $result[$k++] = $points[$i]; |
| 81 | } |
| 82 | |
| 83 | \ksort($result); |
| 84 | |
| 85 | /** @return array<int, array{x:int|float, y:int|float}> */ |
| 86 | return \array_slice($result, 0, $k - 1); |
| 87 | } |
| 88 | |
| 89 | /** |
| 90 | * Sort by x coordinate then by z coordinate |
| 91 | * |
| 92 | * @param array{x:int|float, y:int|float} $a Point a |
| 93 | * @param array{x:int|float, y:int|float} $b Point b |
| 94 | * |
| 95 | * @return float |
| 96 | * |
| 97 | * @since 1.0.0 |
| 98 | */ |
| 99 | private static function sort(array $a, array $b) : float |
| 100 | { |
| 101 | return $a['x'] === $b['x'] ? $a['y'] - $b['y'] : $a['x'] - $b['x']; |
| 102 | } |
| 103 | } |