GEOS  3.11.0beta2
PolygonHoleJoiner.h
1 /**********************************************************************
2  *
3  * GEOS - Geometry Engine Open Source
4  * http://geos.osgeo.org
5  *
6  * Copyright (C) 2020 Paul Ramsey <pramsey@cleverelephant.ca>
7  *
8  * This is free software; you can redistribute and/or modify it under
9  * the terms of the GNU Lesser General Public Licence as published
10  * by the Free Software Foundation.
11  * See the COPYING file for more information.
12  *
13  **********************************************************************/
14 
15 #pragma once
16 
17 #include <geos/geom/Coordinate.h>
18 #include <geos/noding/SegmentSetMutualIntersector.h>
19 
20 #include <unordered_map>
21 #include <vector>
22 
23 // Forward declarations
24 namespace geos {
25 namespace geom {
26 class Envelope;
27 class Geometry;
28 class CoordinateSequence;
29 class LinearRing;
30 }
31 namespace noding {
32 class SegmentString;
33 }
34 }
35 
40 
41 
42 namespace geos {
43 namespace triangulate {
44 namespace polygon {
45 
46 
47 
59 class GEOS_DLL PolygonHoleJoiner {
60 
61 private:
62 
63  // Members
64 
65  static constexpr double EPS = 1.0E-4;
66 
67  std::vector<Coordinate> shellCoords;
68 
69  // orderedCoords is a copy of shellCoords for sort purposes
70  std::set<Coordinate> shellCoordsSorted;
71 
72  // Key: starting end of the cut; Value: list of the other end of the cut
73  std::unordered_map<Coordinate, std::vector<Coordinate>, Coordinate::HashCode> cutMap;
74 
75  std::unique_ptr<noding::SegmentSetMutualIntersector> polygonIntersector;
76  const Polygon* inputPolygon;
77 
78  // The segstrings allocated in createPolygonIntersector need a
79  // place to hold ownership through the lifecycle of the hole joiner
80  std::vector<std::unique_ptr<noding::SegmentString>> polySegStringStore;
81 
82  // Methods
83 
84  static std::vector<Coordinate> ringCoordinates(const LinearRing* ring);
85 
86  void joinHoles();
87 
93  void joinHole(const LinearRing* hole);
94 
102  std::size_t getShellCoordIndex(const Coordinate& shellVertex, const Coordinate& holeVertex);
103 
111  std::size_t getShellCoordIndexSkip(const Coordinate& coord, std::size_t numSkip);
112 
121  std::vector<Coordinate> findLeftShellVertices(const Coordinate& holeCoord);
122 
131  bool isJoinable(const Coordinate& holeCoord, const Coordinate& shellCoord) const;
132 
140  bool crossesPolygon(const Coordinate& p0, const Coordinate& p1) const;
141 
150  void addHoleToShell(std::size_t shellVertexIndex, const CoordinateSequence* holeCoords, std::size_t holeVertexIndex);
151 
158  static std::vector<const LinearRing*> sortHoles(const Polygon* poly);
159 
166  static std::vector<std::size_t> findLeftVertices(const LinearRing* ring);
167 
168  std::unique_ptr<noding::SegmentSetMutualIntersector> createPolygonIntersector(const Polygon* polygon);
169 
170 
171 public:
172 
173  PolygonHoleJoiner(const Polygon* p_inputPolygon);
174 
175  static std::vector<Coordinate> join(const Polygon* inputPolygon);
176  static std::unique_ptr<Polygon> joinAsPolygon(const Polygon* inputPolygon);
177 
183  std::vector<Coordinate> compute();
184 
185 
186 };
187 
188 
189 
190 } // namespace geos.triangulate.polygon
191 } // namespace geos.triangulate
192 } // namespace geos
The internal representation of a list of coordinates inside a Geometry.
Definition: CoordinateSequence.h:44
Coordinate is the lightweight class used to store coordinates.
Definition: Coordinate.h:58
Models an OGC SFS LinearRing. A LinearRing is a LineString which is both closed and simple.
Definition: LinearRing.h:55
Represents a linear polygon, which may include holes.
Definition: Polygon.h:61
Definition: PolygonHoleJoiner.h:59
Basic namespace for all GEOS functionalities.
Definition: Angle.h:25