GEOS  3.10.2
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 triangulate {
32 namespace tri {
33 class TriList;
34 }
35 }
36 namespace noding {
37 class SegmentString;
38 }
39 }
40 
45 
46 
47 namespace geos {
48 namespace triangulate {
49 namespace polygon {
50 
51 
52 
64 class GEOS_DLL PolygonHoleJoiner {
65 
66 private:
67 
68  // Members
69 
70  static constexpr double EPS = 1.0E-4;
71 
72  std::vector<Coordinate> shellCoords;
73 
74  // orderedCoords is a copy of shellCoords for sort purposes
75  std::set<Coordinate> orderedCoords;
76 
77  // Key: starting end of the cut; Value: list of the other end of the cut
78  std::unordered_map<Coordinate, std::vector<Coordinate>, Coordinate::HashCode> cutMap;
79 
80  std::unique_ptr<noding::SegmentSetMutualIntersector> polygonIntersector;
81  const Polygon* inputPolygon;
82 
83  // The segstrings allocated in createPolygonIntersector need a
84  // place to hold ownership through the lifecycle of the hole joiner
85  std::vector<std::unique_ptr<noding::SegmentString>> polySegStringStore;
86 
87  // Methods
88 
89  static std::vector<Coordinate> ringCoordinates(const LinearRing* ring);
90 
91  void joinHoles();
92 
98  void joinHole(const LinearRing* hole);
99 
107  std::size_t getShellCoordIndex(const Coordinate& shellVertex, const Coordinate& holeVertex);
108 
116  std::size_t getShellCoordIndexSkip(const Coordinate& coord, std::size_t numSkip);
117 
126  std::vector<Coordinate> getLeftShellVertex(const Coordinate& holeCoord);
127 
136  bool isJoinable(const Coordinate& holeCoord, const Coordinate& shellCoord) const;
137 
145  bool crossesPolygon(const Coordinate& p0, const Coordinate& p1) const;
146 
155  void addHoleToShell(std::size_t shellVertexIndex, const CoordinateSequence* holeCoords, std::size_t holeVertexIndex);
156 
163  std::vector<const LinearRing*> sortHoles(const Polygon* poly);
164 
171  std::vector<std::size_t> getLeftMostVertex(const LinearRing* ring);
172 
173  std::unique_ptr<noding::SegmentSetMutualIntersector> createPolygonIntersector(const Polygon* polygon);
174 
175 
176 public:
177 
178  PolygonHoleJoiner(const Polygon* p_inputPolygon);
179 
180  static std::vector<Coordinate> join(const Polygon* inputPolygon);
181  static std::unique_ptr<Polygon> joinAsPolygon(const Polygon* inputPolygon);
182 
188  std::vector<Coordinate> compute();
189 
190 
191 };
192 
193 
194 
195 } // namespace geos.triangulate.polygon
196 } // namespace geos.triangulate
197 } // namespace geos
198 
The internal representation of a list of coordinates inside a Geometry.
Definition: CoordinateSequence.h:58
Coordinate is the lightweight class used to store coordinates.
Definition: Coordinate.h:60
Models an OGC SFS LinearRing. A LinearRing is a LineString which is both closed and simple.
Definition: LinearRing.h:57
Represents a linear polygon, which may include holes.
Definition: Polygon.h:64
Definition: PolygonHoleJoiner.h:64
Basic namespace for all GEOS functionalities.
Definition: Angle.h:26