001 // License: GPL. For details, see LICENSE file.
002 package org.openstreetmap.josm.data.osm;
003
004 import static org.openstreetmap.josm.tools.I18n.tr;
005
006 import java.util.ArrayList;
007 import java.util.Collection;
008 import java.util.Collections;
009 import java.util.HashSet;
010 import java.util.List;
011 import java.util.Set;
012
013 import org.openstreetmap.josm.tools.Geometry;
014 import org.openstreetmap.josm.tools.Geometry.PolygonIntersection;
015 import org.openstreetmap.josm.tools.MultiMap;
016
017 public class MultipolygonCreate {
018
019 /**
020 * Represents one polygon that consists of multiple ways.
021 * @author Viesturs
022 *
023 */
024 public static class JoinedPolygon {
025 public final List<Way> ways;
026 public final List<Boolean> reversed;
027 public final List<Node> nodes;
028
029 public JoinedPolygon(List<Way> ways, List<Boolean> reversed) {
030 this.ways = ways;
031 this.reversed = reversed;
032 this.nodes = this.getNodes();
033 }
034
035 /**
036 * Creates a polygon from single way.
037 * @param way
038 */
039 public JoinedPolygon(Way way) {
040 this.ways = Collections.singletonList(way);
041 this.reversed = Collections.singletonList(Boolean.FALSE);
042 this.nodes = this.getNodes();
043 }
044
045
046 /**
047 * Builds a list of nodes for this polygon. First node is not duplicated as last node.
048 * @return
049 */
050 private List<Node> getNodes() {
051 List<Node> nodes = new ArrayList<Node>();
052
053 for(int waypos = 0; waypos < this.ways.size(); waypos ++) {
054 Way way = this.ways.get(waypos);
055 boolean reversed = this.reversed.get(waypos).booleanValue();
056
057 if (!reversed){
058 for (int pos = 0; pos < way.getNodesCount() - 1; pos++) {
059 nodes.add(way.getNode(pos));
060 }
061 }
062 else {
063 for (int pos = way.getNodesCount() - 1; pos > 0; pos--) {
064 nodes.add(way.getNode(pos));
065 }
066 }
067 }
068
069 return nodes;
070 }
071 }
072
073
074 /**
075 * Helper storage class for finding findOuterWays
076 * @author viesturs
077 */
078 static class PolygonLevel {
079 public final int level; //nesting level , even for outer, odd for inner polygons.
080 public final JoinedPolygon outerWay;
081
082 public List<JoinedPolygon> innerWays;
083
084 public PolygonLevel(JoinedPolygon _pol, int _level) {
085 this.outerWay = _pol;
086 this.level = _level;
087 this.innerWays = new ArrayList<JoinedPolygon>();
088 }
089 }
090
091 public List<JoinedPolygon> outerWays;
092 public List<JoinedPolygon> innerWays;
093
094 public MultipolygonCreate(List<JoinedPolygon> outerWays, List<JoinedPolygon> innerWays){
095 this.outerWays = outerWays;
096 this.innerWays = innerWays;
097 }
098
099 public MultipolygonCreate(){
100 this.outerWays = new ArrayList<JoinedPolygon>(0);
101 this.innerWays = new ArrayList<JoinedPolygon>(0);
102 }
103
104 /**
105 * Splits ways into inner and outer JoinedWays. Sets innerWays and outerWays to the result.
106 * TODO: Currently cannot process touching polygons. See code in JoinAreasAction.
107 * @return error description if the ways cannot be split. Null if all fine.
108 */
109 public String makeFromWays(Collection<Way> ways){
110 List<JoinedPolygon> joinedWays = new ArrayList<JoinedPolygon>();
111
112 //collect ways connecting to each node.
113 MultiMap<Node, Way> nodesWithConnectedWays = new MultiMap<Node, Way>();
114 Set<Way> usedWays = new HashSet<Way>();
115
116 for(Way w: ways) {
117 if (w.getNodesCount() < 2) {
118 return tr("Cannot add a way with only {0} nodes.", w.getNodesCount());
119 }
120
121 if (w.isClosed()) {
122 //closed way, add as is.
123 JoinedPolygon jw = new JoinedPolygon(w);
124 joinedWays.add(jw);
125 usedWays.add(w);
126 }
127 else {
128 nodesWithConnectedWays.put(w.lastNode(), w);
129 nodesWithConnectedWays.put(w.firstNode(), w);
130 }
131 }
132
133 //process unclosed ways
134 for (Way startWay: ways) {
135 if (usedWays.contains(startWay)){
136 continue;
137 }
138
139 Node startNode = startWay.firstNode();
140 List<Way> collectedWays = new ArrayList<Way>();
141 List<Boolean> collectedWaysReverse = new ArrayList<Boolean>();
142 Way curWay = startWay;
143 Node prevNode = startNode;
144
145 //find polygon ways
146 while (true) {
147 boolean curWayReverse = prevNode == curWay.lastNode();
148 Node nextNode = (curWayReverse) ? curWay.firstNode(): curWay.lastNode();
149
150 //add cur way to the list
151 collectedWays.add(curWay);
152 collectedWaysReverse.add(Boolean.valueOf(curWayReverse));
153
154 if (nextNode == startNode) {
155 //way finished
156 break;
157 }
158
159 //find next way
160 Collection<Way> adjacentWays = nodesWithConnectedWays.get(nextNode);
161
162 if (adjacentWays.size() != 2) {
163 return tr("Each node must connect exactly 2 ways");
164 }
165
166 Way nextWay = null;
167 for(Way way: adjacentWays){
168 if (way != curWay){
169 nextWay = way;
170 }
171 }
172
173 //move to the next way
174 curWay = nextWay;
175 prevNode = nextNode;
176 }
177
178 usedWays.addAll(collectedWays);
179 joinedWays.add(new JoinedPolygon(collectedWays, collectedWaysReverse));
180 }
181
182 //analyze witch way is inside witch outside.
183 return makeFromPolygons(joinedWays);
184 }
185
186 /**
187 * This method analyzes which ways are inner and which outer. Sets innerWays and outerWays to the result.
188 * @param joinedWays
189 * @return error description if the ways cannot be split. Null if all fine.
190 */
191 private String makeFromPolygons(List<JoinedPolygon> polygons) {
192 List<PolygonLevel> list = findOuterWaysRecursive(0, polygons);
193
194 if (list == null){
195 return tr("There is an intersection between ways.");
196 }
197
198 this.outerWays = new ArrayList<JoinedPolygon>(0);
199 this.innerWays = new ArrayList<JoinedPolygon>(0);
200
201 //take every other level
202 for (PolygonLevel pol : list) {
203 if (pol.level % 2 == 0) {
204 this.outerWays.add(pol.outerWay);
205 }
206 else {
207 this.innerWays.add(pol.outerWay);
208 }
209 }
210
211 return null;
212 }
213
214 /**
215 * Collects outer way and corresponding inner ways from all boundaries.
216 * @param boundaryWays
217 * @return the outermostWay, or null if intersection found.
218 */
219 private List<PolygonLevel> findOuterWaysRecursive(int level, Collection<JoinedPolygon> boundaryWays) {
220
221 //TODO: bad performance for deep nesting...
222 List<PolygonLevel> result = new ArrayList<PolygonLevel>();
223
224 for (JoinedPolygon outerWay : boundaryWays) {
225
226 boolean outerGood = true;
227 List<JoinedPolygon> innerCandidates = new ArrayList<JoinedPolygon>();
228
229 for (JoinedPolygon innerWay : boundaryWays) {
230 if (innerWay == outerWay) {
231 continue;
232 }
233
234 PolygonIntersection intersection = Geometry.polygonIntersection(outerWay.nodes, innerWay.nodes);
235
236 if (intersection == PolygonIntersection.FIRST_INSIDE_SECOND) {
237 outerGood = false; // outer is inside another polygon
238 break;
239 } else if (intersection == PolygonIntersection.SECOND_INSIDE_FIRST) {
240 innerCandidates.add(innerWay);
241 }
242 else if (intersection == PolygonIntersection.CROSSING)
243 {
244 //ways intersect
245 return null;
246 }
247 }
248
249 if (!outerGood) {
250 continue;
251 }
252
253 //add new outer polygon
254 PolygonLevel pol = new PolygonLevel(outerWay, level);
255
256 //process inner ways
257 if (innerCandidates.size() > 0) {
258 List<PolygonLevel> innerList = this.findOuterWaysRecursive(level + 1, innerCandidates);
259 if (innerList == null) {
260 return null; //intersection found
261 }
262
263 result.addAll(innerList);
264
265 for (PolygonLevel pl : innerList) {
266 if (pl.level == level + 1) {
267 pol.innerWays.add(pl.outerWay);
268 }
269 }
270 }
271
272 result.add(pol);
273 }
274
275 return result;
276 }
277 }