GEOS 3.11.2
PolygonHoleJoiner.h
1/**********************************************************************
2 *
3 * GEOS - Geometry Engine Open Source
4 * http://geos.osgeo.org
5 *
6 * Copyright (C) 2023 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/geom/CoordinateSequence.h>
19#include <geos/algorithm/LineIntersector.h>
20#include <geos/noding/SegmentIntersector.h>
21#include <geos/noding/BasicSegmentString.h>
22#include <geos/noding/SegmentSetMutualIntersector.h>
23
24#include <set>
25#include <limits>
26
27// Forward declarations
28namespace geos {
29namespace geom {
30class Envelope;
31class Geometry;
32class LinearRing;
33}
34namespace noding {
35}
36}
37
44
45
46namespace geos {
47namespace triangulate {
48namespace polygon {
49
50
51
68class GEOS_DLL PolygonHoleJoiner {
69
70private:
71
72 // Members
73
74 static constexpr std::size_t NO_INDEX = std::numeric_limits<std::size_t>::max();
75
76 const Polygon* inputPolygon;
77
78 //-- normalized, sorted and noded polygon rings
79 std::unique_ptr<CoordinateSequence> shellRing;
80 std::vector<std::unique_ptr<CoordinateSequence>> holeRings;
81
82 //-- indicates whether a hole should be testing for touching
83 std::vector<bool> isHoleTouchingHint;
84
85 std::vector<Coordinate> joinedRing;
86
87 // a sorted and searchable version of the joinedRing
88 std::set<Coordinate> joinedPts;
89
90 std::unique_ptr<SegmentSetMutualIntersector> boundaryIntersector;
91
92 // holding place for some BasicSegmentStrings
93 std::vector<std::unique_ptr<BasicSegmentString>> polySegStringStore;
94
95
96 // Classes
97 class InteriorIntersectionDetector;
98 friend class PolygonHoleJoiner::InteriorIntersectionDetector;
99
100
101 void extractOrientedRings(const Polygon* polygon);
102 static std::unique_ptr<CoordinateSequence> extractOrientedRing(const LinearRing* ring, bool isCW);
103 void nodeRings();
104 void joinHoles();
105
106 void joinHole(std::size_t index, const CoordinateSequence& holeCoords);
107
115 bool joinTouchingHole(const CoordinateSequence& holeCoords);
116
126 std::size_t findHoleTouchIndex(const CoordinateSequence& holeCoords);
127
133 void joinNonTouchingHole(
134 const CoordinateSequence& holeCoords);
135
136 const Coordinate& findJoinableVertex(
137 const Coordinate& holeJoinCoord);
138
149 std::size_t findJoinIndex(
150 const Coordinate& joinCoord,
151 const Coordinate& holeJoinCoord);
152
162 static bool isLineInterior(
163 const std::vector<Coordinate>& ring,
164 std::size_t ringIndex,
165 const Coordinate& linePt);
166
167 static std::size_t prev(std::size_t i, std::size_t size);
168 static std::size_t next(std::size_t i, std::size_t size);
169
182 void addJoinedHole(
183 std::size_t joinIndex,
184 const CoordinateSequence& holeCoords,
185 std::size_t holeJoinIndex);
186
197 std::vector<Coordinate> createHoleSection(
198 const CoordinateSequence& holeCoords,
199 std::size_t holeJoinIndex,
200 const Coordinate& joinPt);
201
208 static std::vector<const LinearRing*> sortHoles(
209 const Polygon* poly);
210
211 static std::size_t findLowestLeftVertexIndex(
212 const CoordinateSequence& coords);
213
222 bool intersectsBoundary(
223 const Coordinate& p0,
224 const Coordinate& p1);
225
226 std::unique_ptr<SegmentSetMutualIntersector> createBoundaryIntersector();
227
228
229public:
230
231 PolygonHoleJoiner(const Polygon* p_inputPolygon)
232 : inputPolygon(p_inputPolygon)
233 , boundaryIntersector(nullptr)
234 {};
235
243 static std::unique_ptr<Polygon> joinAsPolygon(
244 const Polygon* p_inputPolygon);
245
253 static std::unique_ptr<CoordinateSequence> join(
254 const Polygon* p_inputPolygon);
255
261 std::unique_ptr<CoordinateSequence> compute();
262
263};
264
265
266} // namespace geos.triangulate.polygon
267} // namespace geos.triangulate
268} // 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
Represents a list of contiguous line segments, and supports noding the segments.
Definition BasicSegmentString.h:44
An intersector for the red-blue intersection problem.
Definition SegmentSetMutualIntersector.h:36
Definition PolygonHoleJoiner.h:68
static std::unique_ptr< CoordinateSequence > join(const Polygon *p_inputPolygon)
static std::unique_ptr< Polygon > joinAsPolygon(const Polygon *p_inputPolygon)
std::unique_ptr< CoordinateSequence > compute()
Basic namespace for all GEOS functionalities.
Definition geos.h:39