1<?php
2
3namespace geoPHP\Geometry;
4
5use geoPHP\Exception\InvalidGeometryException;
6use geoPHP\Exception\UnsupportedMethodException;
7use geoPHP\geoPHP;
8
9/**
10 * Polygon: A polygon is a plane figure that is bounded by a closed path,
11 * composed of a finite sequence of straight line segments
12 *
13 * @method LineString[] getComponents()
14 * @property LineString[] $components
15 */
16class Polygon extends Surface
17{
18
19    /**
20     * @param LineString[] $components
21     * @param bool|false $forceCreate
22     * @throws \Exception
23     */
24    public function __construct($components = [], $forceCreate = false)
25    {
26        parent::__construct($components, null, LineString::class);
27
28        foreach ($this->getComponents() as $i => $component) {
29            if ($component->numPoints() < 4) {
30                throw new InvalidGeometryException(
31                    'Cannot create Polygon: Invalid number of points in LinearRing. Found ' .
32                    $component->numPoints() . ', expected more than 3'
33                );
34            }
35            if (!$component->isClosed()) {
36                if ($forceCreate) {
37                    $this->components[$i] = new LineString(
38                        array_merge($component->getComponents(), [$component->startPoint()])
39                    );
40                } else {
41                    throw new InvalidGeometryException(
42                        'Cannot create Polygon: contains non-closed ring (first point: '
43                            . implode(' ', $component->startPoint()->asArray()) . ', last point: '
44                            . implode(' ', $component->endPoint()->asArray()) . ')'
45                    );
46                }
47            }
48            // This check is tooo expensive
49            //if (!$component->isSimple() && !$forceCreate) {
50            //    throw new \Exception('Cannot create Polygon: geometry should be simple');
51            //}
52        }
53    }
54
55    public function geometryType()
56    {
57        return Geometry::POLYGON;
58    }
59
60    public function dimension()
61    {
62        return 2;
63    }
64
65    /**
66     * @param bool|false $exteriorOnly Calculate the area of exterior ring only, or the polygon with holes
67     * @param bool|false $signed       Usually we want to get positive area, but vertices order (CW or CCW) can be determined from signed area.
68     *
69     * @return float|null
70     */
71    public function area($exteriorOnly = false, $signed = false)
72    {
73        if ($this->isEmpty()) {
74            return 0.0;
75        }
76
77        if ($this->getGeos() && $exteriorOnly == false) {
78            // @codeCoverageIgnoreStart
79            /** @noinspection PhpUndefinedMethodInspection */
80            return $this->getGeos()->area();
81            // @codeCoverageIgnoreEnd
82        }
83
84        $exteriorRing = $this->components[0];
85        $points = $exteriorRing->getComponents();
86
87        $pointCount = count($points);
88        if ($pointCount === 0) {
89            return null;
90        }
91        $a = 0.0;
92        foreach ($points as $k => $p) {
93            $j = ($k + 1) % $pointCount;
94            $a = $a + ($p->x() * $points[$j]->y()) - ($p->y() * $points[$j]->x());
95        }
96
97        $area = $signed ? ($a / 2) : abs(($a / 2));
98
99        if ($exteriorOnly == true) {
100            return $area;
101        }
102        foreach ($this->components as $delta => $component) {
103            if ($delta != 0) {
104                $innerPoly = new Polygon([$component]);
105                $area -= $innerPoly->area();
106            }
107        }
108        return $area;
109    }
110
111    /**
112     * @return Point
113     */
114    public function centroid()
115    {
116        if ($this->isEmpty()) {
117            return new Point();
118        }
119
120        if ($this->getGeos()) {
121            // @codeCoverageIgnoreStart
122            /** @noinspection PhpUndefinedMethodInspection */
123            return geoPHP::geosToGeometry($this->getGeos()->centroid());
124            // @codeCoverageIgnoreEnd
125        }
126
127        $x = 0;
128        $y = 0;
129        $totalArea = 0;
130        foreach ($this->getComponents() as $i => $component) {
131            $ca = $this->getRingCentroidAndArea($component);
132            if ($i == 0) {
133                $totalArea += $ca['area'];
134                $x += $ca['x'] * $ca['area'];
135                $y += $ca['y'] * $ca['area'];
136            } else {
137                $totalArea -= $ca['area'];
138                $x += $ca['x'] * $ca['area'] * -1;
139                $y += $ca['y'] * $ca['area'] * -1;
140            }
141        }
142        if ($totalArea == 0.0) {
143            return new Point();
144        }
145        return new Point($x / $totalArea, $y / $totalArea);
146    }
147
148    /**
149     * @param LineString $ring
150     * @return array
151     */
152    protected function getRingCentroidAndArea($ring)
153    {
154        $area = (new Polygon([$ring]))->area(true, true);
155
156        $points = $ring->getPoints();
157        $pointCount = count($points);
158        if ($pointCount === 0 || $area == 0.0) {
159            return ['area' => 0, 'x' => null, 'y' => null];
160        }
161        $x = 0;
162        $y = 0;
163        foreach ($points as $k => $point) {
164            $j = ($k + 1) % $pointCount;
165            $P = ($point->x() * $points[$j]->y()) - ($point->y() * $points[$j]->x());
166            $x += ($point->x() + $points[$j]->x()) * $P;
167            $y += ($point->y() + $points[$j]->y()) * $P;
168        }
169        return ['area' => abs($area), 'x' => $x / (6 * $area), 'y' => $y / (6 * $area)];
170    }
171
172    /**
173     * Find the outermost point from the centroid
174     *
175     * @returns Point The outermost point
176     */
177    public function outermostPoint()
178    {
179        $centroid = $this->centroid();
180        if ($centroid->isEmpty()) {
181            return $centroid;
182        }
183
184        $maxDistance = 0;
185        $maxPoint = null;
186
187        foreach ($this->exteriorRing()->getPoints() as $point) {
188            $distance = $centroid->distance($point);
189
190            if ($distance > $maxDistance) {
191                $maxDistance = $distance;
192                $maxPoint = $point;
193            }
194        }
195
196        return $maxPoint;
197    }
198
199    /**
200     * @return LineString
201     */
202    public function exteriorRing()
203    {
204        if ($this->isEmpty()) {
205            return new LineString();
206        }
207        return $this->components[0];
208    }
209
210    public function numInteriorRings()
211    {
212        if ($this->isEmpty()) {
213            return 0;
214        }
215        return $this->numGeometries() - 1;
216    }
217
218    public function interiorRingN($n)
219    {
220        return $this->geometryN($n + 1);
221    }
222
223    public function isSimple()
224    {
225        if ($this->getGeos()) {
226            // @codeCoverageIgnoreStart
227            /** @noinspection PhpUndefinedMethodInspection */
228            return $this->getGeos()->isSimple();
229            // @codeCoverageIgnoreEnd
230        }
231
232        $segments = $this->explode(true);
233
234        //TODO: instead of this O(n^2) algorithm implement Shamos-Hoey Algorithm which is only O(n*log(n))
235        foreach ($segments as $i => $segment) {
236            foreach ($segments as $j => $checkSegment) {
237                if ($i != $j) {
238                    if (Geometry::segmentIntersects($segment[0], $segment[1], $checkSegment[0], $checkSegment[1])) {
239                        return false;
240                    }
241                }
242            }
243        }
244        return true;
245    }
246
247    /**
248     * For a given point, determine whether it's bounded by the given polygon.
249     * Adapted from @source http://www.assemblysys.com/dataServices/php_pointinpolygon.php
250     *
251     * @see http://en.wikipedia.org/wiki/Point%5Fin%5Fpolygon
252     *
253     * @param Point $point
254     * @param boolean $pointOnBoundary - whether a boundary should be considered "in" or not
255     * @param boolean $pointOnVertex - whether a vertex should be considered "in" or not
256     * @return boolean
257     */
258    public function pointInPolygon($point, $pointOnBoundary = true, $pointOnVertex = true)
259    {
260        $vertices = $this->getPoints();
261
262        // Check if the point sits exactly on a vertex
263        if ($this->pointOnVertex($point, $vertices)) {
264            return $pointOnVertex ? true : false;
265        }
266
267        // Check if the point is inside the polygon or on the boundary
268        $intersections = 0;
269        $verticesCount = count($vertices);
270        for ($i = 1; $i < $verticesCount; $i++) {
271            $vertex1 = $vertices[$i - 1];
272            $vertex2 = $vertices[$i];
273            if (
274                $vertex1->y() == $vertex2->y()
275                && $vertex1->y() == $point->y()
276                && $point->x() > min($vertex1->x(), $vertex2->x())
277                && $point->x() < max($vertex1->x(), $vertex2->x())
278            ) {
279                // Check if point is on an horizontal polygon boundary
280                return $pointOnBoundary ? true : false;
281            }
282            if (
283                $point->y() > min($vertex1->y(), $vertex2->y())
284                && $point->y() <= max($vertex1->y(), $vertex2->y())
285                && $point->x() <= max($vertex1->x(), $vertex2->x())
286                && $vertex1->y() != $vertex2->y()
287            ) {
288                $xinters =
289                        ($point->y() - $vertex1->y()) * ($vertex2->x() - $vertex1->x())
290                        / ($vertex2->y() - $vertex1->y())
291                        + $vertex1->x();
292                if ($xinters == $point->x()) {
293                    // Check if point is on the polygon boundary (other than horizontal)
294                    return $pointOnBoundary ? true : false;
295                }
296                if ($vertex1->x() == $vertex2->x() || $point->x() <= $xinters) {
297                    $intersections++;
298                }
299            }
300        }
301        // If the number of edges we passed through is even, then it's in the polygon.
302        if ($intersections % 2 != 0) {
303            return true;
304        } else {
305            return false;
306        }
307    }
308
309    /**
310     * @param Point $point
311     * @return bool
312     */
313    public function pointOnVertex($point)
314    {
315        foreach ($this->getPoints() as $vertex) {
316            if ($point->equals($vertex)) {
317                return true;
318            }
319        }
320        return false;
321    }
322
323    /**
324     * Checks whether the given geometry is spatially inside the Polygon
325     * TODO: rewrite this. Currently supports point, linestring and polygon with only outer ring
326     * @param Geometry $geometry
327     * @return bool
328     */
329    public function contains(Geometry $geometry)
330    {
331        if ($this->getGeos()) {
332            // @codeCoverageIgnoreStart
333            /** @noinspection PhpUndefinedMethodInspection */
334            return $this->getGeos()->contains($geometry->getGeos());
335            // @codeCoverageIgnoreEnd
336        }
337
338        $isInside = false;
339        foreach ($geometry->getPoints() as $p) {
340            if ($this->pointInPolygon($p)) {
341                $isInside = true; // at least one point of the innerPoly is inside the outerPoly
342                break;
343            }
344        }
345        if (!$isInside) {
346            return false;
347        }
348
349        if ($geometry->geometryType() == Geometry::LINE_STRING) {
350        } elseif ($geometry->geometryType() == Geometry::POLYGON) {
351            $geometry = $geometry->exteriorRing();
352        } else {
353            return false;
354        }
355
356        foreach ($geometry->explode(true) as $innerEdge) {
357            foreach ($this->exteriorRing()->explode(true) as $outerEdge) {
358                if (Geometry::segmentIntersects($innerEdge[0], $innerEdge[1], $outerEdge[0], $outerEdge[1])) {
359                    return false;
360                }
361            }
362        }
363
364        return true;
365    }
366
367    public function getBBox()
368    {
369        return $this->exteriorRing()->getBBox();
370    }
371
372    public function boundary()
373    {
374        // TODO: Implement boundary() method.
375        throw new UnsupportedMethodException(__METHOD__);
376    }
377}
378