Skip to content

Commit ea616f6

Browse files
kamil-tekielakamil-tekiela
committed
Add Gis Value Objects
Signed-off-by: Kamil Tekiela <tekiela246@gmail.com>
1 parent 2400dde commit ea616f6

8 files changed

Lines changed: 434 additions & 339 deletions

File tree

‎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/GisMultiPolygon.php‎

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

88
namespace PhpMyAdmin\Gis;
99

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

@@ -348,20 +349,22 @@ public function generateWkt(array $gisData, int $index, string|null $empty = '')
348349
*/
349350
public function getShape(array $rowData): string
350351
{
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.
352+
// Buffer polygons for further use
353+
/** @var Polygon[] $polygons */
354+
$polygons = [];
354355
foreach ($rowData['parts'] as $i => $ring) {
355-
$rowData['parts'][$i]['isOuter'] = GisPolygon::isOuterRing($ring['points']);
356-
}
356+
$polygons[$i] = Polygon::fromXYArray($ring['points']);
357357

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

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

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

378381
// If the pointOnSurface of the inner ring
379382
// is also inside the outer ring
380-
if (! GisPolygon::isPointInsidePolygon($ring1['pointOnSurface'], $ring2['points'])) {
383+
if (! $ring1['pointOnSurface']->isInsidePolygon($polygons[$k])) {
381384
continue;
382385
}
383386

0 commit comments

Comments
 (0)