GEOS  3.10.1
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 
60 class GEOS_DLL PolygonHoleJoiner {
61 
62 private:
63 
64  // Members
65 
66  static constexpr double EPS = 1.0E-4;
67 
68  std::vector<Coordinate> shellCoords;
69 
70  // orderedCoords is a copy of shellCoords for sort purposes
71  std::set<Coordinate> orderedCoords;
72 
73  // Key: starting end of the cut; Value: list of the other end of the cut
74  std::unordered_map<Coordinate, std::vector<Coordinate>, Coordinate::HashCode> cutMap;
75 
76  std::unique_ptr<noding::SegmentSetMutualIntersector> polygonIntersector;
77  const Polygon* inputPolygon;
78 
79  // The segstrings allocated in createPolygonIntersector need a
80  // place to hold ownership through the lifecycle of the hole joiner
81  std::vector<std::unique_ptr<noding::SegmentString>> polySegStringStore;
82 
83  // Methods
84 
85  static std::vector<Coordinate> ringCoordinates(const LinearRing* ring);
86 
87  void joinHoles();
88 
94  void joinHole(const LinearRing* hole);
95 
103  std::size_t getShellCoordIndex(const Coordinate& shellVertex, const Coordinate& holeVertex);
104 
112  std::size_t getShellCoordIndexSkip(const Coordinate& coord, std::size_t numSkip);
113 
122  std::vector<Coordinate> getLeftShellVertex(const Coordinate& holeCoord);
123 
132  bool isJoinable(const Coordinate& holeCoord, const Coordinate& shellCoord) const;
133 
141  bool crossesPolygon(const Coordinate& p0, const Coordinate& p1) const;
142 
151  void addHoleToShell(std::size_t shellVertexIndex, const CoordinateSequence* holeCoords, std::size_t holeVertexIndex);
152 
159  std::vector<const LinearRing*> sortHoles(const Polygon* poly);
160 
167  std::vector<std::size_t> getLeftMostVertex(const LinearRing* ring);
168 
169  std::unique_ptr<noding::SegmentSetMutualIntersector> createPolygonIntersector(const Polygon* polygon);
170 
171 
172 public:
173 
174  PolygonHoleJoiner(const Polygon* p_inputPolygon);
175 
176  static std::vector<Coordinate> join(const Polygon* inputPolygon);
177  static std::unique_ptr<Polygon> joinAsPolygon(const Polygon* inputPolygon);
178 
184  std::vector<Coordinate> compute();
185 
186 
187 };
188 
189 
190 
191 } // namespace geos.triangulate.polygon
192 } // namespace geos.triangulate
193 } // namespace geos
194 
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:60
Basic namespace for all GEOS functionalities.
Definition: Angle.h:26