1 /**********************************************************************
2 *
3 * GEOS - Geometry Engine Open Source
4 * http://geos.osgeo.org
5 *
6 * Copyright (C) 2020 Paul Ramsey <pramsey@cleverelephant.ca>
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 #include <geos/operation/overlayng/PolygonBuilder.h>
16
17 #include <geos/operation/overlayng/OverlayLabel.h>
18 #include <geos/geom/GeometryFactory.h>
19 #include <geos/util/Assert.h>
20 #include <geos/util/TopologyException.h>
21
22
23
24 namespace geos { // geos
25 namespace operation { // geos.operation
26 namespace overlayng { // geos.operation.overlayng
27
28
29 /*public*/
30 std::vector<std::unique_ptr<Polygon>>
getPolygons()31 PolygonBuilder::getPolygons()
32 {
33 return computePolygons(shellList);
34 }
35
36 /*public*/
37 std::vector<OverlayEdgeRing*>
getShellRings()38 PolygonBuilder::getShellRings()
39 {
40 return shellList;
41 }
42
43 /*private*/
44 std::vector<std::unique_ptr<Polygon>>
computePolygons(std::vector<OverlayEdgeRing * > shells)45 PolygonBuilder::computePolygons(std::vector<OverlayEdgeRing*> shells)
46 {
47 std::vector<std::unique_ptr<Polygon>> resultPolyList;
48 // add Polygons for all shells
49 for (OverlayEdgeRing* er : shells) {
50 std::unique_ptr<Polygon> poly = er->toPolygon(geometryFactory);
51 resultPolyList.push_back(std::move(poly));
52 }
53 return resultPolyList;
54 }
55
56 /*private*/
57 void
buildRings(std::vector<OverlayEdge * > & resultAreaEdges)58 PolygonBuilder::buildRings(std::vector<OverlayEdge*>& resultAreaEdges)
59 {
60 linkResultAreaEdgesMax(resultAreaEdges);
61 std::vector<std::unique_ptr<MaximalEdgeRing>> maxRings = buildMaximalRings(resultAreaEdges);
62 buildMinimalRings(maxRings);
63 placeFreeHoles(shellList, freeHoleList);
64 }
65
66 /*private*/
67 void
linkResultAreaEdgesMax(std::vector<OverlayEdge * > & resultEdges)68 PolygonBuilder::linkResultAreaEdgesMax(std::vector<OverlayEdge*>& resultEdges)
69 {
70 for (OverlayEdge* edge : resultEdges) {
71 // TODO: find some way to skip nodes which are already linked
72 MaximalEdgeRing::linkResultAreaMaxRingAtNode(edge);
73 }
74 }
75
76 /*private*/
77 std::vector<std::unique_ptr<MaximalEdgeRing>>
buildMaximalRings(std::vector<OverlayEdge * > & edges)78 PolygonBuilder::buildMaximalRings(std::vector<OverlayEdge*>& edges)
79 {
80 std::vector<std::unique_ptr<MaximalEdgeRing>> edgeRings;
81 for (OverlayEdge* e : edges) {
82 if (e->isInResultArea() && e->getLabel()->isBoundaryEither()) {
83 // if this edge has not yet been processed
84 if (e->getEdgeRingMax() == nullptr) {
85 // Add a MaximalEdgeRing to the vector
86 edgeRings.emplace_back(new MaximalEdgeRing(e));
87 }
88 }
89 }
90 return edgeRings;
91 }
92
93 /*private*/
94 std::vector<OverlayEdgeRing*>
storeMinimalRings(std::vector<std::unique_ptr<OverlayEdgeRing>> & minRings)95 PolygonBuilder::storeMinimalRings(std::vector<std::unique_ptr<OverlayEdgeRing>>& minRings)
96 {
97 std::vector<OverlayEdgeRing*> minRingPtrs;
98 for (auto& mr: minRings) {
99 minRingPtrs.push_back(mr.get());
100 vecOER.push_back(std::move(mr));
101 }
102 return minRingPtrs;
103 }
104
105 /*private*/
106 void
buildMinimalRings(std::vector<std::unique_ptr<MaximalEdgeRing>> & maxRings)107 PolygonBuilder::buildMinimalRings(std::vector<std::unique_ptr<MaximalEdgeRing>>& maxRings)
108 {
109 for (auto& erMax : maxRings) {
110 auto minRings = erMax->buildMinimalRings(geometryFactory);
111 std::vector<OverlayEdgeRing*> minRingPtrs = storeMinimalRings(minRings);
112 assignShellsAndHoles(minRingPtrs);
113 }
114 }
115
116 /*private*/
117 void
assignShellsAndHoles(std::vector<OverlayEdgeRing * > & minRings)118 PolygonBuilder::assignShellsAndHoles(std::vector<OverlayEdgeRing*>& minRings)
119 {
120 /**
121 * Two situations may occur:
122 * - the rings are a shell and some holes
123 * - rings are a set of holes
124 * This code identifies the situation
125 * and places the rings appropriately
126 */
127 OverlayEdgeRing* shell = findSingleShell(minRings);
128 if (shell != nullptr) {
129 assignHoles(shell, minRings);
130 shellList.push_back(shell);
131 }
132 else {
133 // all rings are holes; their shells will be found later
134 freeHoleList.insert(freeHoleList.end(), minRings.begin(), minRings.end());
135 }
136 }
137
138 /*private*/
139 OverlayEdgeRing*
findSingleShell(std::vector<OverlayEdgeRing * > & edgeRings) const140 PolygonBuilder::findSingleShell(std::vector<OverlayEdgeRing*>& edgeRings) const
141 {
142 std::size_t shellCount = 0;
143 OverlayEdgeRing* shell = nullptr;
144 for (auto er : edgeRings) {
145 if (! er->isHole()) {
146 shell = er;
147 shellCount++;
148 }
149 }
150 util::Assert::isTrue(shellCount <= 1, "found two shells in EdgeRing list");
151 return shell;
152 }
153
154 /*private*/
155 void
assignHoles(OverlayEdgeRing * shell,std::vector<OverlayEdgeRing * > & edgeRings)156 PolygonBuilder::assignHoles(OverlayEdgeRing* shell, std::vector<OverlayEdgeRing*>& edgeRings)
157 {
158 for (auto er : edgeRings) {
159 if (er->isHole()) {
160 er->setShell(shell);
161 }
162 }
163 }
164
165 /*private*/
166 void
placeFreeHoles(std::vector<OverlayEdgeRing * > shells,std::vector<OverlayEdgeRing * > freeHoles)167 PolygonBuilder::placeFreeHoles(std::vector<OverlayEdgeRing*> shells, std::vector<OverlayEdgeRing*> freeHoles)
168 {
169 // TODO: use a spatial index to improve performance
170 for (OverlayEdgeRing* hole : freeHoles) {
171 // only place this hole if it doesn't yet have a shell
172 if (hole->getShell() == nullptr) {
173 OverlayEdgeRing* shell = hole->findEdgeRingContaining(shells);
174 // only when building a polygon-valid result
175 if (isEnforcePolygonal && shell == nullptr) {
176 throw util::TopologyException("unable to assign free hole to a shell", hole->getCoordinate());
177 }
178 hole->setShell(shell);
179 }
180 }
181 }
182
183
184
185
186 } // namespace geos.operation.overlayng
187 } // namespace geos.operation
188 } // namespace geos
189