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 }