Coverage Report

Created: 2026-10-31 06:39

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/src/geos/src/operation/polygonize/EdgeRing.cpp
Line
Count
Source
1
/**********************************************************************
2
 *
3
 * GEOS - Geometry Engine Open Source
4
 * http://geos.osgeo.org
5
 *
6
 * Copyright (C) 2005-2006 Refractions Research Inc.
7
 * Copyright (C) 2001-2002 Vivid Solutions Inc.
8
 *
9
 * This is free software; you can redistribute and/or modify it under
10
 * the terms of the GNU Lesser General Public Licence as published
11
 * by the Free Software Foundation.
12
 * See the COPYING file for more information.
13
 *
14
 **********************************************************************
15
 *
16
 * Last port: operation/polygonize/EdgeRing.java 0b3c7e3eb0d3e
17
 *
18
 **********************************************************************/
19
20
#include <geos/operation/polygonize/EdgeRing.h>
21
#include <geos/operation/polygonize/PolygonizeEdge.h>
22
#include <geos/planargraph/DirectedEdge.h>
23
#include <geos/geom/CoordinateSequence.h>
24
#include <geos/geom/LinearRing.h>
25
#include <geos/geom/Coordinate.h>
26
#include <geos/geom/CoordinateFilter.h>
27
#include <geos/geom/Envelope.h>
28
#include <geos/geom/GeometryFactory.h>
29
#include <geos/geom/util/CurveBuilder.h>
30
#include <geos/algorithm/PointLocation.h>
31
#include <geos/algorithm/Orientation.h>
32
#include <geos/algorithm/locate/IndexedPointInAreaLocator.h>
33
#include <geos/algorithm/locate/SimplePointInAreaLocator.h>
34
#include <geos/util/IllegalArgumentException.h>
35
#include <geos/util.h> // TODO: drop this, includes too much
36
#include <geos/geom/Location.h>
37
38
#include <vector>
39
#include <cassert>
40
41
//#define DEBUG_ALLOC 1
42
//#define GEOS_PARANOIA_LEVEL 2
43
44
45
using namespace geos::planargraph;
46
using namespace geos::algorithm;
47
using namespace geos::geom;
48
49
namespace geos {
50
namespace operation { // geos.operation
51
namespace polygonize { // geos.operation.polygonize
52
53
/*public*/
54
EdgeRing*
55
EdgeRing::findEdgeRingContaining(const std::vector<EdgeRing*> & erList) const
56
0
{
57
0
    EdgeRing* minContainingRing = nullptr;
58
0
    for (auto& edgeRing : erList) {
59
0
        if (edgeRing->contains(*this)) {
60
0
            if (minContainingRing == nullptr
61
0
                || minContainingRing->getEnvelope().contains(edgeRing->getEnvelope())) {
62
0
                minContainingRing = edgeRing;
63
0
            }
64
0
        }
65
0
    }
66
0
    return minContainingRing;
67
0
}
68
69
std::vector<PolygonizeDirectedEdge*>
70
0
EdgeRing::findDirEdgesInRing(PolygonizeDirectedEdge* startDE) {
71
0
    auto de = startDE;
72
0
    std::vector<decltype(de)> edges;
73
74
0
    do {
75
0
        edges.push_back(de);
76
0
        de = de->getNext();
77
0
    } while (de != startDE);
78
79
0
    return edges;
80
0
}
81
82
/*public static*/
83
const CoordinateXY&
84
EdgeRing::ptNotInList(const CoordinateSequence* testPts,
85
                      const CoordinateSequence* pts)
86
0
{
87
0
    const std::size_t npts = testPts->getSize();
88
0
    for(std::size_t i = 0; i < npts; ++i) {
89
0
        const CoordinateXY& testPt = testPts->getAt<CoordinateXY>(i);
90
0
        if(!isInList(testPt, pts)) {
91
0
            return testPt;
92
0
        }
93
0
    }
94
0
    return Coordinate::getNull();
95
0
}
96
97
/*public static*/
98
bool
99
EdgeRing::isInList(const CoordinateXY& pt,
100
                   const CoordinateSequence* pts)
101
0
{
102
0
    const std::size_t npts = pts->getSize();
103
0
    for(std::size_t i = 0; i < npts; ++i) {
104
0
        if(pt == pts->getAt<CoordinateXY>(i)) {
105
0
            return true;
106
0
        }
107
0
    }
108
0
    return false;
109
0
}
110
111
/*public*/
112
EdgeRing::EdgeRing(const GeometryFactory* newFactory)
113
    :
114
0
    factory(newFactory),
115
0
    ring(nullptr),
116
0
    is_hole(false)
117
0
{
118
#ifdef DEBUG_ALLOC
119
    std::cerr << "[" << this << "] EdgeRing(factory)" << std::endl;
120
#endif // DEBUG_ALLOC
121
0
}
122
123
void
124
0
EdgeRing::build(PolygonizeDirectedEdge* startDE) {
125
0
    auto de = startDE;
126
0
    do {
127
0
        add(de);
128
0
        de->setRing(this);
129
0
        de = de->getNext();
130
0
    } while (de != startDE);
131
0
}
132
133
/*public*/
134
void
135
EdgeRing::add(const PolygonizeDirectedEdge* de)
136
0
{
137
0
    deList.push_back(de);
138
0
}
139
140
/*public*/
141
void
142
EdgeRing::computeHole()
143
0
{
144
0
    getRingInternal();
145
146
0
    if (ring->getGeometryTypeId() == GEOS_COMPOUNDCURVE) {
147
0
        auto coords = ring->getCoordinates();
148
0
        is_hole = Orientation::isCCW(coords.get());
149
0
    } else {
150
0
        const SimpleCurve* sc = detail::down_cast<SimpleCurve*>(ring.get());
151
0
        is_hole = Orientation::isCCW(sc->getCoordinatesRO());
152
0
    }
153
0
}
154
155
/*public*/
156
void
157
EdgeRing::addHole(std::unique_ptr<Curve> hole)
158
0
{
159
0
    holes.push_back(std::move(hole));
160
0
}
161
162
void
163
0
EdgeRing::addHole(EdgeRing* holeER) {
164
0
    holeER->setShell(this);
165
0
    auto hole = holeER->getRingOwnership(); // TODO is this right method?
166
0
    addHole(std::move(hole));
167
0
}
168
169
/*public*/
170
std::unique_ptr<Surface>
171
EdgeRing::getPolygon()
172
0
{
173
0
    if (!holes.empty()) {
174
0
        return factory->createSurface(std::move(ring), std::move(holes));
175
0
    } else {
176
0
        return factory->createSurface(std::move(ring));
177
0
    }
178
0
}
179
180
// Adapter class to check whether a point lies within a ring.
181
// Unlike IndexedPointInAreaLocator, SimplePointInAreaLocator does not treat
182
// closed rings as areas.
183
class PointInCurvedRingLocator : public algorithm::locate::PointOnGeometryLocator {
184
    public:
185
0
        explicit PointInCurvedRingLocator(const Curve& ring) : m_ring(ring) {}
186
187
0
        geom::Location locate(const geom::CoordinateXY* p) override {
188
0
            return PointLocation::locateInRing(*p, m_ring);
189
0
        }
190
191
    private:
192
        const Curve& m_ring;
193
};
194
195
algorithm::locate::PointOnGeometryLocator*
196
EdgeRing::getLocator() const
197
0
{
198
0
    if (ringLocator == nullptr) {
199
0
        const auto* rng = getRingInternal();
200
0
        if (rng->hasCurvedComponents()) {
201
0
            ringLocator = std::make_unique<PointInCurvedRingLocator>(*rng);
202
0
        } else {
203
0
            ringLocator = std::make_unique<algorithm::locate::IndexedPointInAreaLocator>(*rng);
204
0
        }
205
0
    }
206
0
    return ringLocator.get();
207
0
}
208
209
/*public*/
210
bool
211
EdgeRing::isValid() const
212
0
{
213
0
    return is_valid;
214
0
}
215
216
void
217
EdgeRing::computeValid()
218
0
{
219
0
    const Curve* r = getRingInternal();
220
221
0
    if (r->getNumPoints() <= 3) {
222
0
        is_valid = false;
223
0
        return;
224
0
    }
225
226
0
    if (r->getGeometryTypeId() == GEOS_LINEARRING) {
227
0
        is_valid = getRingInternal()->isValid();
228
0
    } else {
229
        // TODO: Change once IsValidOp supports curves
230
0
        is_valid = true;
231
0
    }
232
0
}
233
234
bool
235
0
EdgeRing::contains(const EdgeRing& otherRing) const {
236
    // the test envelope must be properly contained
237
    // (guards against testing rings against themselves)
238
0
    const Envelope& env = getEnvelope();
239
0
    const Envelope& testEnv = otherRing.getEnvelope();
240
0
    if (! env.containsProperly(testEnv)) {
241
0
        return false;
242
0
    }
243
0
    return isPointInOrOut(otherRing);
244
0
  }
245
246
bool
247
0
EdgeRing::isPointInOrOut(const EdgeRing& otherRing) const {
248
    // in most cases only one or two points will be checked
249
250
0
    struct PointTester : public CoordinateFilter {
251
252
0
    public:
253
0
        explicit PointTester(const EdgeRing* p_ring) : m_er(p_ring), m_result(false) {}
254
255
0
        void filter_ro(const CoordinateXY* pt) override {
256
0
            Location loc = m_er->locate(*pt);
257
258
0
            if (loc == geom::Location::INTERIOR) {
259
0
                m_done = true;
260
0
                m_result = true;
261
0
            } else if (loc == geom::Location::EXTERIOR) {
262
0
                m_done = true;
263
0
                m_result = false;
264
0
            }
265
266
            // pt is on BOUNDARY, so keep checking for a determining location
267
0
        }
268
269
0
        bool isDone() const override {
270
0
            return m_done;
271
0
        }
272
273
0
        bool getResult() const {
274
0
            return m_result;
275
0
        }
276
277
0
    private:
278
0
        const EdgeRing* m_er;
279
0
        bool m_done{false};
280
0
        bool m_result;
281
0
    };
282
283
0
    PointTester tester(this);
284
0
    otherRing.getRingInternal()->apply_ro(&tester);
285
286
0
    return tester.getResult();
287
0
}
288
289
/*private*/
290
const Curve*
291
EdgeRing::getRingInternal() const
292
0
{
293
0
    if (ring == nullptr) {
294
0
        bool hasZ = false;
295
0
        bool hasM = false;
296
297
0
        for(const auto& de : deList) {
298
0
            const auto edge = detail::down_cast<PolygonizeEdge*>(de->getEdge());
299
0
            hasZ |= edge->getLine()->hasZ();
300
0
            hasM |= edge->getLine()->hasM();
301
0
        }
302
303
0
        geom::util::CurveBuilder builder(*factory, hasZ, hasM);
304
305
0
        for(const auto& de : deList) {
306
0
            const auto edge = detail::down_cast<PolygonizeEdge*>(de->getEdge());
307
0
            const bool isCurved = edge->getLine()->getGeometryTypeId() == GEOS_CIRCULARSTRING;
308
0
            const bool isForward = de->getEdgeDirection();
309
310
0
            builder.add(*edge->getLine()->getCoordinatesRO(), isCurved, isForward);
311
0
        }
312
313
0
        builder.matchRingZM();
314
0
        ring = builder.getGeometry();
315
0
    }
316
317
0
    return ring.get();
318
0
}
319
320
/*public*/
321
std::unique_ptr<Curve>
322
EdgeRing::getRingOwnership()
323
0
{
324
0
    getRingInternal(); // active lazy generation
325
0
    return std::move(ring);
326
0
}
327
328
EdgeRing*
329
0
EdgeRing::getOuterHole() const {
330
    // Only shells can have outer holes
331
0
    if (isHole()) {
332
0
        return nullptr;
333
0
    }
334
335
    // A shell is an outer shell if any edge is also in an outer hole.
336
    // A hole is an outer shell if it is not contained by a shell.
337
0
    for (auto& de : deList) {
338
0
        auto adjRing = (dynamic_cast<PolygonizeDirectedEdge*>(de->getSym()))->getRing();
339
0
        if (adjRing->isOuterHole()) {
340
0
            return adjRing;
341
0
        }
342
0
    }
343
344
0
    return nullptr;
345
0
}
346
347
void
348
0
EdgeRing::updateIncludedRecursive() {
349
0
    visitedByUpdateIncludedRecursive = true;
350
351
0
    if (isHole()) {
352
0
        return;
353
0
    }
354
355
0
    for (const auto& de : deList) {
356
0
        auto adjShell = (dynamic_cast<const PolygonizeDirectedEdge*>(de->getSym()))->getRing()->getShell();
357
358
0
        if (adjShell != nullptr) {
359
0
            if (!adjShell->isIncludedSet() && !adjShell->visitedByUpdateIncludedRecursive) {
360
0
                adjShell->updateIncludedRecursive();
361
0
            }
362
0
        }
363
0
    }
364
365
0
    for (const auto& de : deList) {
366
0
        auto adjShell = (dynamic_cast<const PolygonizeDirectedEdge*>(de->getSym()))->getRing()->getShell();
367
368
0
        if (adjShell != nullptr) {
369
0
            if (adjShell->isIncludedSet()) {
370
0
                setIncluded(!adjShell->isIncluded());
371
0
                return;
372
0
            }
373
0
        }
374
0
    }
375
376
0
}
377
378
} // namespace geos.operation.polygonize
379
} // namespace geos.operation
380
} // namespace geos