Coverage Report

Created: 2026-10-31 06:47

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/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