Coverage Report

Created: 2026-10-31 06:44

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/src/geos/src/operation/valid/PolygonRing.cpp
Line
Count
Source
1
/**********************************************************************
2
 *
3
 * GEOS - Geometry Engine Open Source
4
 * http://geos.osgeo.org
5
 *
6
 * Copyright (C) 2021 Paul Ramsey <pramsey@cleverelephant.ca>
7
 * Copyright (C) 2021 Martin Davis
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
#include <geos/algorithm/Orientation.h>
17
#include <geos/geom/Coordinate.h>
18
#include <geos/geom/LinearRing.h>
19
#include <geos/operation/valid/PolygonRing.h>
20
21
#include <stack>
22
23
using namespace geos::geom;
24
25
namespace geos {      // geos
26
namespace operation { // geos.operation
27
namespace valid {     // geos.operation.valid
28
29
30
/* public static */
31
bool
32
PolygonRing::isShell(const PolygonRing* polyRing)
33
0
{
34
0
    if (polyRing == nullptr) return true;
35
0
    return polyRing->isShell();
36
0
}
37
38
39
/* public static */
40
bool
41
PolygonRing::addTouch(PolygonRing* ring0, PolygonRing* ring1, const CoordinateXY& pt)
42
0
{
43
    //--- skip if either polygon does not have holes
44
0
    if (ring0 == nullptr || ring1 == nullptr)
45
0
      return false;
46
47
    //--- only record touches within a polygon
48
0
    if (! ring0->isSamePolygon(ring1)) return false;
49
50
0
    if (! ring0->isOnlyTouch(ring1, pt)) return true;
51
0
    if (! ring1->isOnlyTouch(ring0, pt)) return true;
52
53
0
    ring0->addTouch(ring1, pt);
54
0
    ring1->addTouch(ring0, pt);
55
0
    return false;
56
0
}
57
58
59
/* public static */
60
const CoordinateXY*
61
PolygonRing::findHoleCycleLocation(const std::vector<PolygonRing*>& polyRings)
62
0
{
63
0
    for (PolygonRing* polyRing : polyRings) {
64
0
        if (! polyRing->isInTouchSet()) {
65
0
            const CoordinateXY* holeCycleLoc = polyRing->findHoleCycleLocation();
66
0
            if (holeCycleLoc != nullptr) return holeCycleLoc;
67
0
        }
68
0
    }
69
0
    return nullptr;
70
0
}
71
72
73
/* public static */
74
const CoordinateXY*
75
PolygonRing::findInteriorSelfNode(const std::vector<PolygonRing*>& polyRings)
76
0
{
77
0
    for (const PolygonRing* polyRing : polyRings) {
78
0
        const CoordinateXY* interiorSelfNode = polyRing->findInteriorSelfNode();
79
0
        if (interiorSelfNode != nullptr) {
80
0
            return interiorSelfNode;
81
0
        }
82
0
    }
83
0
    return nullptr;
84
0
}
85
86
87
/* private */
88
std::vector<PolygonRingTouch*>
89
PolygonRing::getTouches() const
90
0
{
91
0
    std::vector<PolygonRingTouch*> touchesVect;
92
0
    for (auto& mapEntry: touches) {
93
0
        PolygonRingTouch* touch = const_cast<PolygonRingTouch*>(&mapEntry.second);
94
0
        touchesVect.push_back(touch);
95
0
    }
96
0
    return touchesVect;
97
0
}
98
99
100
/* private */
101
void
102
PolygonRing::addTouch(PolygonRing* polyRing, const CoordinateXY& pt)
103
0
{
104
0
    std::size_t nTouches = touches.count(polyRing->id);
105
0
    if (nTouches == 0) {
106
        // uses pair's piecewise constructor to emplace into
107
        // std::map<int, PolygonRingTouch> touches;
108
0
        touches.emplace(std::piecewise_construct,
109
0
              std::forward_as_tuple(polyRing->id),
110
0
              std::forward_as_tuple(polyRing, pt));
111
0
    };
112
0
}
113
114
115
/* public */
116
void
117
PolygonRing::addSelfTouch(const CoordinateXY& origin,
118
    const CoordinateXY* e00, const CoordinateXY* e01,
119
    const CoordinateXY* e10, const CoordinateXY* e11)
120
0
{
121
0
    selfNodes.emplace_back(origin, e00, e01, e10, e11);
122
0
}
123
124
125
/* private */
126
bool
127
PolygonRing::isOnlyTouch(const PolygonRing* polyRing, const CoordinateXY& pt) const
128
0
{
129
    //--- no touches for this ring
130
0
    if (touches.empty()) return true;
131
    //--- no touches for other ring
132
133
    // std::map.find() returns std::pair
134
0
    auto search = touches.find(polyRing->id);
135
    // Not found
136
0
    if (search == touches.end()) return true;
137
    // Found
138
0
    const PolygonRingTouch& touch = search->second;
139
    //--- the rings touch - check if point is the same
140
0
    return touch.isAtLocation(pt);
141
0
}
142
143
144
/* private */
145
const CoordinateXY*
146
PolygonRing::findHoleCycleLocation()
147
0
{
148
    //--- the touch set including this ring is already processed
149
0
    if (isInTouchSet()) return nullptr;
150
151
    //--- scan the touch set tree rooted at this ring
152
    // Assert: this.touchSetRoot is null
153
0
    PolygonRing* root = this;
154
0
    root->setTouchSetRoot(root);
155
156
0
    if (! hasTouches())
157
0
        return nullptr;
158
159
0
    std::stack<PolygonRingTouch*> touchStack;
160
0
    init(root, touchStack);
161
162
0
    while (! touchStack.empty()) {
163
0
        const PolygonRingTouch* touch = touchStack.top();
164
0
        touchStack.pop();
165
0
        const CoordinateXY* holeCyclePt = scanForHoleCycle(touch, root, touchStack);
166
0
        if (holeCyclePt != nullptr) {
167
0
            return holeCyclePt;
168
0
        }
169
0
    }
170
0
    return nullptr;
171
0
}
172
173
174
/* private static */
175
void
176
PolygonRing::init(PolygonRing* root, std::stack<PolygonRingTouch*>& touchStack)
177
0
{
178
0
    for (PolygonRingTouch* touch : root->getTouches()) {
179
0
        touch->getRing()->setTouchSetRoot(root);
180
0
        touchStack.push(touch);
181
0
    }
182
0
}
183
184
185
/* private */
186
const CoordinateXY*
187
PolygonRing::scanForHoleCycle(const PolygonRingTouch* currentTouch,
188
    PolygonRing* root,
189
    std::stack<PolygonRingTouch*>& touchStack)
190
0
{
191
0
    const PolygonRing* polyRing = currentTouch->getRing();
192
0
    const CoordinateXY* currentPt = currentTouch->getCoordinate();
193
194
    /**
195
     * Scan the touched rings
196
     * Either they form a hole cycle, or they are added to the touch set
197
     * and pushed on the stack for scanning
198
     */
199
0
    for (PolygonRingTouch* touch : polyRing->getTouches()) {
200
        /**
201
        * Don't check touches at the entry point
202
        * to avoid trivial cycles.
203
        * They will already be processed or on the stack
204
        * from the previous ring (which touched
205
        * all the rings at that point as well)
206
        */
207
0
        if (currentPt->equals2D(*touch->getCoordinate()))
208
0
            continue;
209
210
        /**
211
        * Test if the touched ring has already been
212
        * reached via a different touch path.
213
        * This is indicated by it already being marked as
214
        * part of the touch set.
215
        * This indicates a hole cycle has been found.
216
        */
217
0
        PolygonRing* touchRing = touch->getRing();
218
0
        if (touchRing->getTouchSetRoot() == root)
219
0
            return touch->getCoordinate();
220
221
0
        touchRing->setTouchSetRoot(root);
222
223
0
        touchStack.push(touch);
224
0
    }
225
0
    return nullptr;
226
0
}
227
228
229
/* public */
230
const CoordinateXY*
231
PolygonRing::findInteriorSelfNode() const
232
0
{
233
0
    if (selfNodes.empty()) return nullptr;
234
235
    /**
236
     * Determine if the ring interior is on the Right.
237
     * This is the case if the ring is a shell and is CW,
238
     * or is a hole and is CCW.
239
     */
240
0
    bool isCCW = algorithm::Orientation::isCCW(ring->getCoordinatesRO());
241
0
    bool isInteriorOnRight = isShell() ^ isCCW;
242
243
0
    for (const PolygonRingSelfNode& selfNode : selfNodes) {
244
0
        if (!selfNode.isExterior(isInteriorOnRight)) {
245
0
            return selfNode.getCoordinate();
246
0
        }
247
0
    }
248
0
    return nullptr;
249
0
}
250
251
252
253
} // namespace geos.operation.valid
254
} // namespace geos.operation
255
} // namespace geos