/src/geos/src/noding/GeometryNoder.cpp
Line | Count | Source |
1 | | /********************************************************************** |
2 | | * |
3 | | * GEOS - Geometry Engine Open Source |
4 | | * http://geos.osgeo.org |
5 | | * |
6 | | * Copyright (C) 2012 Sandro Santilli <strk@kbt.io> |
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 | | * NOTE: this is not in JTS. JTS has a snapround/GeometryNoder though |
16 | | * |
17 | | **********************************************************************/ |
18 | | |
19 | | #include <geos/algorithm/CircularArcIntersector.h> |
20 | | |
21 | | #include <geos/geom/Geometry.h> |
22 | | #include <geos/geom/PrecisionModel.h> |
23 | | #include <geos/geom/CoordinateSequence.h> |
24 | | #include <geos/geom/CompoundCurve.h> |
25 | | #include <geos/geom/GeometryFactory.h> |
26 | | #include <geos/geom/CircularString.h> |
27 | | #include <geos/geom/MultiCurve.h> |
28 | | #include <geos/geom/LineString.h> |
29 | | |
30 | | #include <geos/noding/ArcIntersectionAdder.h> |
31 | | #include <geos/noding/GeometryNoder.h> |
32 | | #include <geos/noding/DirectionIndependentArcString.h> |
33 | | #include <geos/noding/IteratedNoder.h> |
34 | | #include <geos/noding/MCIndexNoder.h> |
35 | | #include <geos/noding/NodableArcString.h> |
36 | | #include <geos/noding/NodedSegmentString.h> |
37 | | #include <geos/noding/Noder.h> |
38 | | #include <geos/noding/OrientedCoordinateArray.h> |
39 | | #include <geos/noding/SegmentString.h> |
40 | | #include <geos/noding/SimpleNoder.h> |
41 | | |
42 | | #include <geos/util/Assert.h> |
43 | | |
44 | | #include <memory> // for unique_ptr |
45 | | #include <set> |
46 | | #include <unordered_set> |
47 | | |
48 | | using geos::geom::CoordinateXY; |
49 | | using geos::geom::SimpleCurve; |
50 | | using geos::geom::Geometry; |
51 | | |
52 | | |
53 | | namespace geos { |
54 | | namespace noding { // geos.noding |
55 | | |
56 | | namespace { |
57 | | |
58 | | /** |
59 | | * Add every linear element in a geometry into PathString vector |
60 | | */ |
61 | | class PathStringExtractor: public geom::GeometryComponentFilter { |
62 | | public: |
63 | | PathStringExtractor(std::vector<std::unique_ptr<PathString>> & to, |
64 | | bool constructZ, |
65 | | bool constructM) |
66 | 15.3k | : _to(to) |
67 | 15.3k | , _constructZ(constructZ) |
68 | 15.3k | , _constructM(constructM) |
69 | 15.3k | , _foundCompoundCurve(false) |
70 | 15.3k | {} |
71 | | |
72 | 15.3k | bool foundCompoundCurve() const { |
73 | 15.3k | return _foundCompoundCurve; |
74 | 15.3k | } |
75 | | |
76 | | void |
77 | | filter_ro(const Geometry* g) override |
78 | 899k | { |
79 | 899k | if (g->isEmpty()) { |
80 | 102k | return; |
81 | 102k | } |
82 | | |
83 | 797k | if(const auto* ls = dynamic_cast<const geom::LineString*>(g)) { |
84 | 13.1k | auto coord = ls->getSharedCoordinates(); |
85 | 13.1k | auto ss = std::make_unique<NodedSegmentString>(coord, _constructZ, _constructM, ls); |
86 | 13.1k | _to.push_back(std::move(ss)); |
87 | 783k | } else if (const auto* cs = dynamic_cast<const geom::CircularString*>(g)) { |
88 | 2.48k | const auto& coords = cs->getSharedCoordinates(); |
89 | 2.48k | auto arcs = cs->getArcs(); |
90 | | |
91 | 2.48k | auto as = std::make_unique<NodableArcString>(std::move(arcs), coords, _constructZ, _constructM, cs); |
92 | 2.48k | _to.push_back(std::move(as)); |
93 | 781k | } else if (const auto* cc = dynamic_cast<const geom::CompoundCurve*>(g)) { |
94 | 0 | _foundCompoundCurve = true; |
95 | 0 | for (std::size_t i = 0; i < cc->getNumCurves(); i++) { |
96 | 0 | filter_ro(cc->getCurveN(i)); |
97 | 0 | } |
98 | 0 | } |
99 | 797k | } |
100 | | private: |
101 | | std::vector<std::unique_ptr<PathString>>& _to; |
102 | | bool _constructZ; |
103 | | bool _constructM; |
104 | | bool _foundCompoundCurve; |
105 | | |
106 | | PathStringExtractor(PathStringExtractor const&); /*= delete*/ |
107 | | PathStringExtractor& operator=(PathStringExtractor const&); /*= delete*/ |
108 | | }; |
109 | | |
110 | | /** Class to construct a geometry from a set of PathStrings, given the |
111 | | * geometry from which they originated. This allows CompoundCurves to |
112 | | * be reconstructed. Unlike CurveBuilder, PathStrings will not be |
113 | | * joined into SimpleCurves. |
114 | | */ |
115 | | class CurveRebuilder { |
116 | | |
117 | | public: |
118 | 0 | explicit CurveRebuilder(const Geometry& g) : m_srcGeom(g) {} |
119 | | |
120 | | // Register a PathString with the rebuilder |
121 | | // The context of the PathString will be set to nullptr during computation. |
122 | | void add(PathString* path) |
123 | 0 | { |
124 | 0 | const auto& coords = path->getCoordinates(); |
125 | |
|
126 | 0 | m_pathForStartPoint[coords->front<CoordinateXY>()].push_back(path); |
127 | 0 | m_pathForContext[path->getData()].push_back(path); |
128 | 0 | } |
129 | | |
130 | | // Prevent reconstruction of CompoundCurve across the starting |
131 | | // or ending nodes of a specified PathString. |
132 | | void disableNodes(const PathString* path) |
133 | 0 | { |
134 | 0 | const CoordinateXY& startPoint = path->getCoordinates()->front<CoordinateXY>(); |
135 | 0 | const CoordinateXY& endPoint = path->getCoordinates()->back<CoordinateXY>(); |
136 | |
|
137 | 0 | doNotContinueFromNode(startPoint); |
138 | 0 | doNotContinueFromNode(endPoint); |
139 | 0 | } |
140 | | |
141 | | std::unique_ptr<Geometry> getGeometry() |
142 | 0 | { |
143 | 0 | collectGeoms(m_srcGeom); |
144 | |
|
145 | 0 | return m_srcGeom.getFactory()->buildGeometry(std::move(m_resultGeoms)); |
146 | 0 | } |
147 | | |
148 | | private: |
149 | 0 | void doNotContinueFromNode(const CoordinateXY& p) { |
150 | 0 | m_pathForStartPoint.erase(p); |
151 | 0 | } |
152 | | |
153 | | void collectGeoms(const Geometry& g) |
154 | 0 | { |
155 | 0 | if (dynamic_cast<const geom::GeometryCollection*>(&g)) { |
156 | 0 | for (std::size_t i = 0; i < g.getNumGeometries(); i++) { |
157 | 0 | collectGeoms(*g.getGeometryN(i)); |
158 | 0 | } |
159 | 0 | return; |
160 | 0 | } |
161 | | |
162 | 0 | const auto geomType = g.getGeometryTypeId(); |
163 | |
|
164 | 0 | if (geomType == geom::GEOS_LINESTRING) { |
165 | 0 | auto it = m_pathForContext.find(&g); |
166 | 0 | util::Assert::isTrue(it != m_pathForContext.end()); |
167 | |
|
168 | 0 | for (auto& path : it->second) { |
169 | 0 | m_resultGeoms.push_back(getFactory().createLineString(path->getCoordinates())); |
170 | 0 | } |
171 | 0 | } else if (geomType == geom::GEOS_CIRCULARSTRING) { |
172 | 0 | auto it = m_pathForContext.find(&g); |
173 | 0 | util::Assert::isTrue(it != m_pathForContext.end()); |
174 | |
|
175 | 0 | for (auto& path : it->second) { |
176 | 0 | m_resultGeoms.push_back(getFactory().createCircularString(path->getCoordinates())); |
177 | 0 | } |
178 | 0 | } else if (geomType == geom::GEOS_COMPOUNDCURVE) { |
179 | 0 | collectCompoundCurveGeoms(*detail::down_cast<const geom::CompoundCurve *>(&g)); |
180 | 0 | } else { |
181 | 0 | throw util::UnsupportedOperationException("Unsupported geometry type: " + g.getGeometryType()); |
182 | 0 | } |
183 | 0 | } |
184 | | |
185 | | void collectCompoundCurveGeoms(const geom::CompoundCurve& cc) |
186 | 0 | { |
187 | 0 | for (std::size_t i = 0; i < cc.getNumCurves(); i++) { |
188 | 0 | std::vector<std::unique_ptr<SimpleCurve>> curves; |
189 | |
|
190 | 0 | const SimpleCurve* sc = cc.getCurveN(i); |
191 | 0 | const CoordinateXY& originalEndPoint = sc->getCoordinatesRO()->back<CoordinateXY>(); |
192 | |
|
193 | 0 | auto it = m_pathForContext.find(sc); |
194 | 0 | util::Assert::isTrue(it != m_pathForContext.end()); |
195 | |
|
196 | 0 | const auto& pathsForCurve = it->second; |
197 | |
|
198 | 0 | for (auto& path : pathsForCurve) { |
199 | 0 | if (path->getData() == nullptr) { |
200 | 0 | continue; |
201 | 0 | } |
202 | 0 | path->setData(nullptr); |
203 | |
|
204 | 0 | const CoordinateXY& endPoint = path->getCoordinates()->back<CoordinateXY>(); |
205 | 0 | std::unique_ptr<SimpleCurve> geom = getPathGeometry(*path); |
206 | |
|
207 | 0 | if (endPoint == originalEndPoint) { |
208 | 0 | curves.push_back(std::move(geom)); |
209 | 0 | } else { |
210 | 0 | m_resultGeoms.push_back(std::move(geom)); |
211 | 0 | } |
212 | 0 | } |
213 | |
|
214 | 0 | if (!curves.empty()) { |
215 | 0 | auto it2 = m_pathForStartPoint.find(originalEndPoint); |
216 | 0 | while (it2 != m_pathForStartPoint.end()) { |
217 | 0 | const auto& next = it2->second; |
218 | 0 | it2 = m_pathForStartPoint.end(); |
219 | |
|
220 | 0 | if (next.size() == 1) { |
221 | 0 | PathString* path = next[0]; |
222 | |
|
223 | 0 | auto nextIndex = i + curves.size(); |
224 | 0 | if (nextIndex < cc.getNumCurves() && path->getData() == cc.getCurveN(nextIndex)) { |
225 | 0 | curves.push_back(getPathGeometry(*path)); |
226 | 0 | path->setData(nullptr); |
227 | |
|
228 | 0 | const CoordinateXY& endPoint = path->getCoordinates()->back<CoordinateXY>(); |
229 | 0 | it2 = m_pathForStartPoint.find(endPoint); |
230 | 0 | } |
231 | 0 | } |
232 | 0 | } |
233 | |
|
234 | 0 | if (curves.size() == 1) { |
235 | 0 | m_resultGeoms.push_back(std::move(curves[0])); |
236 | 0 | } else { |
237 | 0 | m_resultGeoms.push_back(getFactory().createCompoundCurve(std::move(curves))); |
238 | 0 | } |
239 | 0 | } |
240 | 0 | } |
241 | 0 | } |
242 | | |
243 | | std::unique_ptr<SimpleCurve> |
244 | | getPathGeometry(const PathString& path) const |
245 | 0 | { |
246 | 0 | const bool isLinear = dynamic_cast<const SegmentString*>(&path); |
247 | |
|
248 | 0 | if (isLinear) { |
249 | 0 | return getFactory().createLineString(path.getCoordinates()); |
250 | 0 | } |
251 | | |
252 | 0 | return getFactory().createCircularString(path.getCoordinates()); |
253 | 0 | } |
254 | | |
255 | | const geom::GeometryFactory& |
256 | | getFactory() const |
257 | 0 | { |
258 | 0 | return *m_srcGeom.getFactory(); |
259 | 0 | } |
260 | | |
261 | | const Geometry& m_srcGeom; |
262 | | |
263 | | std::map<CoordinateXY, std::vector<PathString*>> m_pathForStartPoint; |
264 | | std::map<const void*, std::vector<PathString*>> m_pathForContext; |
265 | | |
266 | | std::vector<std::unique_ptr<Geometry>> m_resultGeoms; |
267 | | }; |
268 | | |
269 | | } |
270 | | |
271 | | |
272 | | /* public static */ |
273 | | std::unique_ptr<geom::Geometry> |
274 | | GeometryNoder::node(const geom::Geometry& geom) |
275 | 15.4k | { |
276 | 15.4k | GeometryNoder noder(geom); |
277 | 15.4k | return noder.getNoded(); |
278 | 15.4k | } |
279 | | |
280 | | std::unique_ptr<geom::Geometry> |
281 | | GeometryNoder::node(const geom::Geometry& geom1, const geom::Geometry& geom2) |
282 | 0 | { |
283 | 0 | GeometryNoder noder(geom1, geom2); |
284 | 0 | return noder.getNoded(); |
285 | 0 | } |
286 | | |
287 | | /* public */ |
288 | | GeometryNoder::GeometryNoder(const geom::Geometry& g) |
289 | | : |
290 | 15.4k | argGeom1(&g), |
291 | 15.4k | argGeom2(nullptr), |
292 | 15.4k | argGeomHasCurves(g.hasCurvedComponents()), |
293 | 15.4k | argGeomHasCompoundCurves(false), |
294 | 15.4k | onlyFirstGeomEdges(false), |
295 | 15.4k | preserveCompoundCurves(false) |
296 | 15.4k | {} |
297 | | |
298 | | GeometryNoder::GeometryNoder(const geom::Geometry& g1, const geom::Geometry& g2) |
299 | | : |
300 | 0 | argGeom1(&g1), |
301 | 0 | argGeom2(&g2), |
302 | 0 | argGeomHasCurves(g1.hasCurvedComponents() || g2.hasCurvedComponents()), |
303 | 0 | argGeomHasCompoundCurves(false), |
304 | 0 | onlyFirstGeomEdges(false), |
305 | 0 | preserveCompoundCurves(false) |
306 | 0 | {} |
307 | | |
308 | 15.4k | GeometryNoder::~GeometryNoder() = default; |
309 | | |
310 | | bool |
311 | | GeometryNoder::isInResult(const PathString& ps) const |
312 | 1.10M | { |
313 | 1.10M | return !onlyFirstGeomEdges || ps.getData() != nullptr; |
314 | 1.10M | } |
315 | | |
316 | | /* private */ |
317 | | std::unique_ptr<geom::Geometry> |
318 | | GeometryNoder::toGeometry(std::vector<std::unique_ptr<PathString>>& nodedEdges) const |
319 | 12.1k | { |
320 | 12.1k | const geom::GeometryFactory* geomFact = argGeom1->getFactory(); |
321 | | |
322 | 12.1k | std::set< OrientedCoordinateArray > ocas; |
323 | 12.1k | std::unordered_set<DirectionIndependentArcString> arcStrings; |
324 | | |
325 | 12.1k | std::vector<PathString*> pathsToKeep; |
326 | | |
327 | 1.10M | for(auto& path : nodedEdges) { |
328 | 1.10M | if (!isInResult(*path)) { |
329 | 0 | continue; |
330 | 0 | } |
331 | | |
332 | 1.10M | if (const auto* as = dynamic_cast<const ArcString*>(path.get())) { |
333 | | // Check if an equivalent arc is known |
334 | 316k | if (arcStrings.emplace(*as).second) { |
335 | 211k | pathsToKeep.push_back(path.get()); |
336 | 211k | } |
337 | 785k | } else { |
338 | 785k | const auto& coords = path->getCoordinates(); |
339 | 785k | OrientedCoordinateArray oca1(*coords); |
340 | | |
341 | | // Check if an equivalent edge is known |
342 | 785k | if(ocas.insert(oca1).second) { |
343 | 323k | pathsToKeep.push_back(path.get()); |
344 | 323k | } |
345 | 785k | } |
346 | 1.10M | } |
347 | | |
348 | 12.1k | if (preserveCompoundCurves && argGeomHasCompoundCurves) { |
349 | 0 | util::Assert::isTrue(onlyFirstGeomEdges); |
350 | |
|
351 | 0 | CurveRebuilder rebuilder(*argGeom1); |
352 | |
|
353 | 0 | for (auto& path : pathsToKeep) { |
354 | 0 | rebuilder.add(path); |
355 | 0 | } |
356 | | |
357 | | // Any edge that begins at a point where a geomB edge starts/ends is not |
358 | | // eligible for merging. |
359 | 0 | for (auto& path : nodedEdges) { |
360 | 0 | if (!isInResult(*path)) { |
361 | 0 | rebuilder.disableNodes(path.get()); |
362 | 0 | } |
363 | 0 | } |
364 | |
|
365 | 0 | return rebuilder.getGeometry(); |
366 | 0 | } |
367 | | |
368 | | // Create a geometry out of the noded substrings. |
369 | 12.1k | std::vector<std::unique_ptr<geom::Geometry>> lines; |
370 | 12.1k | lines.reserve(nodedEdges.size()); |
371 | 12.1k | bool resultArcs = false; |
372 | | |
373 | 531k | for (const auto& path : pathsToKeep) { |
374 | 531k | const auto& coords = path->getCoordinates(); |
375 | | |
376 | 531k | const bool isLinear = dynamic_cast<const SegmentString*>(path); |
377 | | |
378 | 531k | if (isLinear) { |
379 | 323k | lines.push_back(geomFact->createLineString(coords)); |
380 | 323k | } else { |
381 | 208k | resultArcs = true; |
382 | 208k | lines.push_back(geomFact->createCircularString(coords)); |
383 | 208k | } |
384 | 531k | } |
385 | | |
386 | 12.1k | if (resultArcs) { |
387 | 2.01k | return geomFact->createMultiCurve(std::move(lines)); |
388 | 10.1k | } else { |
389 | 10.1k | return geomFact->createMultiLineString(std::move(lines)); |
390 | 10.1k | } |
391 | 12.1k | } |
392 | | |
393 | | /* public */ |
394 | | std::unique_ptr<geom::Geometry> |
395 | | GeometryNoder::getNoded() |
396 | 15.4k | { |
397 | 15.4k | if (argGeom1->isEmpty() && (argGeom2 == nullptr || argGeom2->isEmpty())) |
398 | 60 | return argGeom1->clone(); |
399 | | |
400 | 15.3k | std::vector<std::unique_ptr<PathString>> lineList; |
401 | | |
402 | 15.3k | extractPathStrings(*argGeom1, lineList); |
403 | 15.3k | if (argGeom2 != nullptr) { |
404 | 0 | std::vector<std::unique_ptr<PathString>> lineList2; |
405 | 0 | extractPathStrings(*argGeom2, lineList2); |
406 | 0 | for (auto& path : lineList2) { |
407 | 0 | path->setData(nullptr); // prevent from appearing in result |
408 | 0 | lineList.push_back(std::move(path)); |
409 | 0 | } |
410 | 0 | } |
411 | | |
412 | 15.3k | Noder& p_noder = getNoder(); |
413 | 15.3k | p_noder.computePathNodes(PathString::toRawPointerVector(lineList)); |
414 | 15.3k | auto nodedEdges = p_noder.getNodedPaths(); |
415 | | |
416 | 15.3k | std::unique_ptr<geom::Geometry> noded = toGeometry(nodedEdges); |
417 | | |
418 | 15.3k | return noded; |
419 | 15.4k | } |
420 | | |
421 | | /* private static */ |
422 | | void |
423 | | GeometryNoder::extractPathStrings(const geom::Geometry& g, |
424 | | std::vector<std::unique_ptr<PathString>>& to) |
425 | 15.3k | { |
426 | 15.3k | PathStringExtractor ex(to, g.hasZ(), g.hasM()); |
427 | 15.3k | g.apply_ro(&ex); |
428 | 15.3k | argGeomHasCompoundCurves |= ex.foundCompoundCurve(); |
429 | 15.3k | } |
430 | | |
431 | | /* private */ |
432 | | Noder& |
433 | | GeometryNoder::getNoder() |
434 | 15.3k | { |
435 | 15.3k | if(!noder) { |
436 | 15.3k | const geom::PrecisionModel* pm = argGeom1->getFactory()->getPrecisionModel(); |
437 | 15.3k | if (argGeomHasCurves) { |
438 | 2.48k | noder = std::make_unique<SimpleNoder>(); |
439 | | |
440 | 2.48k | m_cai = std::make_unique<algorithm::CircularArcIntersector>(argGeom1->getPrecisionModel()); |
441 | 2.48k | m_aia = std::make_unique<ArcIntersectionAdder>(*m_cai); |
442 | 2.48k | detail::down_cast<SimpleNoder*>(noder.get())->setArcIntersector(*m_aia); |
443 | 12.8k | } else { |
444 | 12.8k | noder = std::make_unique<IteratedNoder>(pm); |
445 | 12.8k | } |
446 | 15.3k | } |
447 | 15.3k | return *noder; |
448 | 15.3k | } |
449 | | |
450 | | void |
451 | | GeometryNoder::setOnlyFirstGeomEdges(bool p_onlyFirstGeomEdges) |
452 | 0 | { |
453 | 0 | onlyFirstGeomEdges = p_onlyFirstGeomEdges; |
454 | 0 | } |
455 | | |
456 | | void |
457 | | GeometryNoder::setPreserveCompoundCurves(bool preserve) |
458 | 0 | { |
459 | 0 | preserveCompoundCurves = preserve; |
460 | 0 | } |
461 | | |
462 | | } // namespace geos.noding |
463 | | } // namespace geos |