1
|
|
|
<?php |
2
|
|
|
|
3
|
|
|
declare(strict_types=1); |
4
|
|
|
|
5
|
|
|
namespace Location\Processor\Polyline; |
6
|
|
|
|
7
|
|
|
use Location\GeometryInterface; |
8
|
|
|
use Location\Line; |
9
|
|
|
use Location\Polygon; |
10
|
|
|
use Location\Polyline; |
11
|
|
|
use Location\Utility\PerpendicularDistance; |
12
|
|
|
use RuntimeException; |
13
|
|
|
|
14
|
|
|
/** |
15
|
|
|
* /** |
16
|
|
|
* Simplify Polyline with the Douglas-Peucker-Algorithm |
17
|
|
|
* |
18
|
|
|
* The Algorithm is described here: |
19
|
|
|
* http://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm |
20
|
|
|
* |
21
|
|
|
* The formula for the Perpendicular Distance is described here: |
22
|
|
|
* http://biodiversityinformatics.amnh.org/open_source/pdc/documentation.php |
23
|
|
|
* |
24
|
|
|
* @author Marcus Jaschen <[email protected]> |
25
|
|
|
*/ |
26
|
|
|
class SimplifyDouglasPeucker implements SimplifyInterface |
27
|
|
|
{ |
28
|
|
|
/** |
29
|
|
|
* @var float |
30
|
|
|
*/ |
31
|
|
|
protected $tolerance; |
32
|
|
|
|
33
|
|
|
/** |
34
|
|
|
* @param float $tolerance the perpendicular distance threshold in meters |
35
|
|
|
*/ |
36
|
|
|
public function __construct(float $tolerance) |
37
|
|
|
{ |
38
|
|
|
$this->tolerance = $tolerance; |
39
|
|
|
} |
40
|
|
|
|
41
|
|
|
/** |
42
|
|
|
* @param Polyline $polyline |
43
|
|
|
* |
44
|
|
|
* @return Polyline |
45
|
|
|
* @throws RuntimeException |
46
|
|
|
*/ |
47
|
|
View Code Duplication |
public function simplify(Polyline $polyline): Polyline |
|
|
|
|
48
|
|
|
{ |
49
|
|
|
$result = $this->simplifyGeometry($polyline); |
50
|
|
|
|
51
|
|
|
if (!($result instanceof Polyline)) { |
52
|
|
|
throw new RuntimeException('Result is no Polyline', 9737647468); |
53
|
|
|
} |
54
|
|
|
|
55
|
|
|
return $result; |
56
|
|
|
} |
57
|
|
|
|
58
|
|
|
/** |
59
|
|
|
* This method is a workaround to allow simplifying polygons too. It'll be |
60
|
|
|
* merged with `simplify()` in the next major release. |
61
|
|
|
* |
62
|
|
|
* @param GeometryInterface $geometry |
63
|
|
|
* |
64
|
|
|
* @return GeometryInterface |
65
|
|
|
*/ |
66
|
|
|
public function simplifyGeometry(GeometryInterface $geometry): GeometryInterface |
67
|
|
|
{ |
68
|
|
|
if (!($geometry instanceof Polyline) && !($geometry instanceof Polygon)) { |
69
|
|
|
return $geometry; |
70
|
|
|
} |
71
|
|
|
|
72
|
|
|
$counterPoints = $geometry->getNumberOfPoints(); |
73
|
|
|
|
74
|
|
View Code Duplication |
if ($geometry instanceof Polygon) { |
|
|
|
|
75
|
|
|
if ($counterPoints <= 3) { |
76
|
|
|
return clone $geometry; |
77
|
|
|
} |
78
|
|
|
$result = new Polygon(); |
79
|
|
|
} else { |
80
|
|
|
if ($counterPoints < 3) { |
81
|
|
|
return clone $geometry; |
82
|
|
|
} |
83
|
|
|
$result = new Polyline(); |
84
|
|
|
} |
85
|
|
|
|
86
|
|
|
$simplifiedLine = $this->douglasPeucker($geometry->getPoints()); |
87
|
|
|
|
88
|
|
|
$result->addPoints($simplifiedLine); |
89
|
|
|
|
90
|
|
|
return $result; |
91
|
|
|
} |
92
|
|
|
|
93
|
|
|
/** |
94
|
|
|
* @param array $line |
95
|
|
|
* |
96
|
|
|
* @return array |
97
|
|
|
*/ |
98
|
|
|
protected function douglasPeucker(array $line): array |
99
|
|
|
{ |
100
|
|
|
$distanceMax = 0; |
101
|
|
|
$index = 0; |
102
|
|
|
|
103
|
|
|
$lineSize = count($line); |
104
|
|
|
|
105
|
|
|
$pdCalc = new PerpendicularDistance(); |
106
|
|
|
|
107
|
|
|
for ($i = 1; $i <= ($lineSize - 2); $i++) { |
108
|
|
|
$distance = $pdCalc->getPerpendicularDistance($line[$i], new Line($line[0], $line[$lineSize - 1])); |
109
|
|
|
|
110
|
|
|
if ($distance > $distanceMax) { |
111
|
|
|
$index = $i; |
112
|
|
|
$distanceMax = $distance; |
113
|
|
|
} |
114
|
|
|
} |
115
|
|
|
|
116
|
|
|
if ($distanceMax > $this->tolerance) { |
117
|
|
|
$lineSplitFirst = array_slice($line, 0, $index + 1); |
118
|
|
|
$lineSplitSecond = array_slice($line, $index, $lineSize - $index); |
119
|
|
|
|
120
|
|
|
$resultsSplit1 = count($lineSplitFirst) > 2 |
121
|
|
|
? $this->douglasPeucker($lineSplitFirst) |
122
|
|
|
: $lineSplitFirst; |
123
|
|
|
|
124
|
|
|
$resultsSplit2 = count($lineSplitSecond) > 2 |
125
|
|
|
? $this->douglasPeucker($lineSplitSecond) |
126
|
|
|
: $lineSplitSecond; |
127
|
|
|
|
128
|
|
|
array_pop($resultsSplit1); |
129
|
|
|
|
130
|
|
|
return array_merge($resultsSplit1, $resultsSplit2); |
131
|
|
|
} |
132
|
|
|
|
133
|
|
|
return [$line[0], $line[$lineSize - 1]]; |
134
|
|
|
} |
135
|
|
|
} |
136
|
|
|
|
Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation.
You can also find more detailed suggestions in the “Code” section of your repository.