Skip to content

Commit 25dd2fb

Browse files
MauricioFauthMauricioFauth
authored
Merge pull request #18384 from kamil-tekiela/GisPolygon-shapes
Gis polygon shapes
2 parents 9481236 + 15bfd74 commit 25dd2fb

23 files changed

Lines changed: 456 additions & 466 deletions

‎libraries/classes/Gis/Ds/Point.php‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
<?php
2+
3+
declare(strict_types=1);
4+
5+
namespace PhpMyAdmin\Gis\Ds;
6+
7+
use function max;
8+
use function min;
9+
10+
final class Point
11+
{
12+
public function __construct(public readonly float $x, public readonly float $y)
13+
{
14+
}
15+
16+
/**
17+
* Determines whether a given point is inside a given polygon.
18+
*/
19+
public function isInsidePolygon(Polygon $polygon): bool
20+
{
21+
$noOfPoints = $polygon->count();
22+
23+
// If first point is repeated at the end remove it
24+
if ($polygon->top() == $polygon->bottom()) {
25+
--$noOfPoints;
26+
}
27+
28+
$counter = 0;
29+
30+
// Use ray casting algorithm
31+
$p1 = $polygon->bottom();
32+
for ($i = 1; $i <= $noOfPoints; $i++) {
33+
$p2 = $polygon[$i % $noOfPoints];
34+
if ($this->y <= min($p1->y, $p2->y)) {
35+
$p1 = $p2;
36+
continue;
37+
}
38+
39+
if ($this->y > max($p1->y, $p2->y)) {
40+
$p1 = $p2;
41+
continue;
42+
}
43+
44+
if ($this->x > max($p1->x, $p2->x)) {
45+
$p1 = $p2;
46+
continue;
47+
}
48+
49+
if ($p1->y != $p2->y) {
50+
$xinters = ($this->y - $p1->y)
51+
* ($p2->x - $p1->x)
52+
/ ($p2->y - $p1->y) + $p1->x;
53+
if ($p1->x == $p2->x || $this->x <= $xinters) {
54+
$counter++;
55+
}
56+
}
57+
58+
$p1 = $p2;
59+
}
60+
61+
return $counter % 2 !== 0;
62+
}
63+
}

‎libraries/classes/Gis/Ds/Polygon.php‎

Lines changed: 132 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,132 @@
1+
<?php
2+
3+
declare(strict_types=1);
4+
5+
namespace PhpMyAdmin\Gis\Ds;
6+
7+
use SplDoublyLinkedList;
8+
9+
use function count;
10+
use function sqrt;
11+
12+
/** @extends SplDoublyLinkedList<Point> */
13+
final class Polygon extends SplDoublyLinkedList
14+
{
15+
/** @param non-empty-list<array{x: float, y: float}> $points */
16+
public static function fromXYArray(array $points): self
17+
{
18+
$polygon = new self();
19+
foreach ($points as $pointXY) {
20+
$polygon[] = new Point($pointXY['x'], $pointXY['y']);
21+
}
22+
23+
return $polygon;
24+
}
25+
26+
/**
27+
* Calculates the area of a closed simple polygon.
28+
*/
29+
public function area(): float
30+
{
31+
$noOfPoints = $this->count();
32+
33+
// If the last point is same as the first point ignore it
34+
if ($this->top() == $this->bottom()) {
35+
--$noOfPoints;
36+
}
37+
38+
// _n-1
39+
// A = _1_ \ (X(i) * Y(i+1)) - (Y(i) * X(i+1))
40+
// 2 /__
41+
// i=0
42+
$area = 0;
43+
for ($i = 0; $i < $noOfPoints; $i++) {
44+
$j = ($i + 1) % $noOfPoints;
45+
$area += $this[$i]->x * $this[$j]->y;
46+
$area -= $this[$i]->y * $this[$j]->x;
47+
}
48+
49+
$area /= 2.0;
50+
51+
return $area;
52+
}
53+
54+
/**
55+
* Determines whether a set of points represents an outer ring.
56+
* If points are in clockwise orientation then, they form an outer ring.
57+
*/
58+
public function isOuterRing(): bool
59+
{
60+
// If area is negative then it's in clockwise orientation,
61+
// i.e. it's an outer ring
62+
return $this->area() < 0;
63+
}
64+
65+
/**
66+
* Returns a point that is guaranteed to be on the surface of the ring.
67+
* (for simple closed rings)
68+
*
69+
* @return Point|false a point on the surface of the ring
70+
*/
71+
public function getPointOnSurface(): Point|false
72+
{
73+
$points = $this->findTwoConsecutiveDistinctPoints();
74+
75+
if ($points === false) {
76+
return false;
77+
}
78+
79+
$pointPrev = $points[0];
80+
$pointNext = $points[1];
81+
82+
// Find the mid point
83+
$midPoint = new Point(($pointPrev->x + $pointNext->x) / 2, ($pointPrev->y + $pointNext->y) / 2);
84+
85+
// Always keep $epsilon < 1 to go with the reduction logic down here
86+
$epsilon = 0.1;
87+
$denominator = sqrt(($pointNext->y - $pointPrev->y) ** 2 + ($pointPrev->x - $pointNext->x) ** 2);
88+
89+
while (true) {
90+
// Get the points on either sides of the line
91+
// with a distance of epsilon to the mid point
92+
$x = $midPoint->x + ($epsilon * ($pointNext->y - $pointPrev->y)) / $denominator;
93+
$y = $midPoint->y + ($x - $midPoint->x) * ($pointPrev->x - $pointNext->x) / ($pointNext->y - $pointPrev->y);
94+
$pointA = new Point($x, $y);
95+
96+
$x = $midPoint->x + ($epsilon * ($pointNext->y - $pointPrev->y)) / (0 - $denominator);
97+
$y = $midPoint->y + ($x - $midPoint->x) * ($pointPrev->x - $pointNext->x) / ($pointNext->y - $pointPrev->y);
98+
$pointB = new Point($x, $y);
99+
100+
// One of the points should be inside the polygon,
101+
// unless epsilon chosen is too large
102+
if ($pointA->isInsidePolygon($this)) {
103+
return $pointA;
104+
}
105+
106+
if ($pointB->isInsidePolygon($this)) {
107+
return $pointB;
108+
}
109+
110+
//If both are outside the polygon reduce the epsilon and
111+
//recalculate the points(reduce exponentially for faster convergence)
112+
$epsilon **= 2;
113+
if ($epsilon == 0) {
114+
return false;
115+
}
116+
}
117+
}
118+
119+
/** @return array{Point, Point}|false */
120+
private function findTwoConsecutiveDistinctPoints(): array|false
121+
{
122+
for ($i = 0, $nb = count($this) - 1; $i < $nb; $i++) {
123+
$pointPrev = $this->offsetGet($i);
124+
$pointNext = $this->offsetGet($i + 1);
125+
if ($pointPrev->y !== $pointNext->y) {
126+
return [$pointNext, $pointPrev];
127+
}
128+
}
129+
130+
return false;
131+
}
132+
}

libraries/classes/Gis/ScaleData.php renamed to libraries/classes/Gis/Ds/ScaleData.php

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22

33
declare(strict_types=1);
44

5-
namespace PhpMyAdmin\Gis;
5+
namespace PhpMyAdmin\Gis\Ds;
66

77
use function max;
88
use function min;

‎libraries/classes/Gis/GisGeometry.php‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,7 @@
77

88
namespace PhpMyAdmin\Gis;
99

10+
use PhpMyAdmin\Gis\Ds\ScaleData;
1011
use PhpMyAdmin\Image\ImageWrapper;
1112
use TCPDF;
1213

‎libraries/classes/Gis/GisGeometryCollection.php‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@
88
namespace PhpMyAdmin\Gis;
99

1010
use ErrorException;
11+
use PhpMyAdmin\Gis\Ds\ScaleData;
1112
use PhpMyAdmin\Image\ImageWrapper;
1213
use TCPDF;
1314

‎libraries/classes/Gis/GisLineString.php‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,7 @@
77

88
namespace PhpMyAdmin\Gis;
99

10+
use PhpMyAdmin\Gis\Ds\ScaleData;
1011
use PhpMyAdmin\Image\ImageWrapper;
1112
use TCPDF;
1213

‎libraries/classes/Gis/GisMultiLineString.php‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,7 @@
77

88
namespace PhpMyAdmin\Gis;
99

10+
use PhpMyAdmin\Gis\Ds\ScaleData;
1011
use PhpMyAdmin\Image\ImageWrapper;
1112
use TCPDF;
1213

‎libraries/classes/Gis/GisMultiPoint.php‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,7 @@
77

88
namespace PhpMyAdmin\Gis;
99

10+
use PhpMyAdmin\Gis\Ds\ScaleData;
1011
use PhpMyAdmin\Image\ImageWrapper;
1112
use TCPDF;
1213

‎libraries/classes/Gis/GisMultiPolygon.php‎

Lines changed: 14 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,8 @@
77

88
namespace PhpMyAdmin\Gis;
99

10+
use PhpMyAdmin\Gis\Ds\Polygon;
11+
use PhpMyAdmin\Gis\Ds\ScaleData;
1012
use PhpMyAdmin\Image\ImageWrapper;
1113
use TCPDF;
1214

@@ -348,20 +350,22 @@ public function generateWkt(array $gisData, int $index, string|null $empty = '')
348350
*/
349351
public function getShape(array $rowData): string
350352
{
351-
// Determines whether each line ring is an inner ring or an outer ring.
352-
// If it's an inner ring get a point on the surface which can be used to
353-
// correctly classify inner rings to their respective outer rings.
353+
// Buffer polygons for further use
354+
/** @var Polygon[] $polygons */
355+
$polygons = [];
354356
foreach ($rowData['parts'] as $i => $ring) {
355-
$rowData['parts'][$i]['isOuter'] = GisPolygon::isOuterRing($ring['points']);
356-
}
357+
$polygons[$i] = Polygon::fromXYArray($ring['points']);
357358

358-
// Find points on surface for inner rings
359-
foreach ($rowData['parts'] as $i => $ring) {
360-
if ($ring['isOuter']) {
359+
// Determines whether each line ring is an inner ring or an outer ring.
360+
// If it's an inner ring get a point on the surface which can be used to
361+
// correctly classify inner rings to their respective outer rings.
362+
$rowData['parts'][$i]['isOuter'] = $polygons[$i]->isOuterRing();
363+
if ($rowData['parts'][$i]['isOuter']) {
361364
continue;
362365
}
363366

364-
$rowData['parts'][$i]['pointOnSurface'] = GisPolygon::getPointOnSurface($ring['points']);
367+
// Find points on surface for inner rings
368+
$rowData['parts'][$i]['pointOnSurface'] = $polygons[$i]->getPointOnSurface();
365369
}
366370

367371
// Classify inner rings to their respective outer rings.
@@ -377,7 +381,7 @@ public function getShape(array $rowData): string
377381

378382
// If the pointOnSurface of the inner ring
379383
// is also inside the outer ring
380-
if (! GisPolygon::isPointInsidePolygon($ring1['pointOnSurface'], $ring2['points'])) {
384+
if (! $ring1['pointOnSurface']->isInsidePolygon($polygons[$k])) {
381385
continue;
382386
}
383387

‎libraries/classes/Gis/GisPoint.php‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,7 @@
77

88
namespace PhpMyAdmin\Gis;
99

10+
use PhpMyAdmin\Gis\Ds\ScaleData;
1011
use PhpMyAdmin\Image\ImageWrapper;
1112
use TCPDF;
1213

0 commit comments

Comments
 (0)