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