GEOS 3.15.0dev
BoundaryChainNoder.h
1/**********************************************************************
2 *
3 * GEOS - Geometry Engine Open Source
4 * http://geos.osgeo.org
5 *
6 * Copyright (c) Martin Davis 2022
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/noding/Noder.h> // for composition
18#include <geos/noding/SegmentString.h> // for composition
19#include <geos/geom/LineSegment.h> // for composition
20#include <geos/noding/BasicSegmentString.h>
21
22#include <unordered_set>
23
24// Forward declarations
25namespace geos {
26namespace geom {
27class CoordinateSequence;
28class Coordinate;
29}
30namespace noding {
31class NodedSegmentString;
32}
33}
34
35namespace geos { // geos
36namespace noding { // geos::noding
37
56class GEOS_DLL BoundaryChainNoder : public Noder {
58
59private:
60
61 class BoundaryChainMap {
62
63 private:
64
65 // Members
66 SegmentString* segString;
67 std::vector<bool> isBoundary;
68
69 static SegmentString* createChain(
70 const SegmentString* segString,
71 std::size_t startIndex,
72 std::size_t endIndex,
73 bool constructZ,
74 bool constructM);
75
76 std::size_t findChainStart(std::size_t index) const;
77 std::size_t findChainEnd(std::size_t index) const;
78
79 public:
80
81 BoundaryChainMap(SegmentString* ss)
82 : segString(ss) {
83 isBoundary.resize(ss->size()-1, false);
84 };
85
86 void setBoundarySegment(std::size_t index);
87 void createChains(std::vector<SegmentString*>& chains, bool constructZ, bool constructM);
88 };
89
90 class Segment {
91 public:
92 Segment(const geom::CoordinateSequence& seq,
93 BoundaryChainMap& segMap,
94 std::size_t index)
95 : m_seq(seq)
96 , m_segMap(segMap)
97 , m_index(index)
98 , m_flip(seq.getAt<geom::CoordinateXY>(index).compareTo(seq.getAt<geom::CoordinateXY>(index + 1)) < 0)
99 {}
100
101 const geom::CoordinateXY& p0() const {
102 return m_seq.getAt<geom::CoordinateXY>(m_flip ? m_index : m_index + 1);
103 }
104
105 const geom::CoordinateXY& p1() const {
106 return m_seq.getAt<geom::CoordinateXY>(m_flip ? m_index + 1 : m_index);
107 }
108
109 void markBoundary() const {
110 m_segMap.setBoundarySegment(m_index);
111 };
112
113 bool operator==(const Segment& other) const {
114 return p0().equals2D(other.p0()) && p1().equals2D(other.p1());
115 }
116
117 struct HashCode {
118 std::size_t operator()(const Segment& s) const {
119 std::size_t h = std::hash<double>{}(s.p0().x);
120 h ^= (std::hash<double>{}(s.p0().y) << 1);
121 h ^= (std::hash<double>{}(s.p1().x) << 1);
122 h ^= (std::hash<double>{}(s.p1().y) << 1);
123 return h;
124 }
125 };
126
127 private:
128 const geom::CoordinateSequence& m_seq;
129 BoundaryChainMap& m_segMap;
130 std::size_t m_index;
131 bool m_flip;
132 };
133
134
135public:
136
137 using SegmentSet = std::unordered_set<Segment, Segment::HashCode>;
138
140 : m_chainList(nullptr)
141 , m_constructZ(false)
142 , m_constructM(false)
143 {};
144
145 // Noder virtual methods
146 std::vector<SegmentString*>* getNodedSubstrings() const override;
147 void computeNodes(std::vector<SegmentString*>* inputSegStrings) override;
148
149
150private:
151
152 // Members
153 std::vector<SegmentString*>* m_chainList;
154 std::vector<std::unique_ptr<geom::CoordinateSequence>> m_substrings;
155 bool m_constructZ;
156 bool m_constructM;
157
158 // Methods
159 void addSegments(std::vector<SegmentString*>* segStrings,
160 SegmentSet& segSet,
161 std::vector<BoundaryChainMap>& includedSegs);
162
163 static void addSegments(SegmentString* segString,
164 BoundaryChainMap& segInclude,
165 SegmentSet& segSet);
166
167 static bool segSetContains(
168 SegmentSet& segSet, Segment& seg);
169
170 static void markBoundarySegments(SegmentSet& segSet);
171
172 std::vector<SegmentString*>* extractChains(std::vector<BoundaryChainMap>& sections) const;
173
174 Coordinate::UnorderedSet findNodePts(
175 const std::vector<SegmentString*>* segStrings) const;
176
177 std::vector<SegmentString*>* nodeChains(
178 const std::vector<SegmentString*>* chains,
179 const Coordinate::UnorderedSet& nodePts);
180
181 void nodeChain(
182 SegmentString* chain,
183 const Coordinate::UnorderedSet& nodePts,
184 std::vector<SegmentString*>* nodedChains);
185
186 std::size_t findNodeIndex(
187 const SegmentString* chain,
188 std::size_t start,
189 const Coordinate::UnorderedSet& nodePts) const;
190
192 const SegmentString* segString,
193 std::size_t start, std::size_t end);
194
195 // Declared as non-copyable
197 BoundaryChainNoder& operator=(const BoundaryChainNoder& rhs);
198
199};
200
201} // namespace geos::noding
202} // namespace geos
The internal representation of a list of coordinates inside a Geometry.
Definition CoordinateSequence.h:56
Coordinate is the lightweight class used to store coordinates.
Definition Coordinate.h:217
Represents a list of contiguous line segments, and supports noding the segments.
Definition BasicSegmentString.h:44
Definition BoundaryChainNoder.h:56
std::vector< SegmentString * > * getNodedSubstrings() const override
Returns a collection of fully noded SegmentStrings. The SegmentStrings have the same context as their...
void computeNodes(std::vector< SegmentString * > *inputSegStrings) override
Computes the noding for a collection of SegmentStrings.
Computes all intersections between segments in a set of SegmentString.
Definition Noder.h:46
An interface for classes which represent a sequence of contiguous line segments.
Definition SegmentString.h:47
const T & getAt(std::size_t i) const
Returns a read-only reference to Coordinate at position i.
Definition CoordinateSequence.h:249
Basic namespace for all GEOS functionalities.
Definition geos.h:38