/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 |