001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.data.osm; 003 004import static org.openstreetmap.josm.tools.I18n.tr; 005 006import java.util.ArrayList; 007import java.util.Collection; 008import java.util.Collections; 009import java.util.HashSet; 010import java.util.List; 011import java.util.Set; 012 013import org.openstreetmap.josm.tools.Geometry; 014import org.openstreetmap.josm.tools.Geometry.PolygonIntersection; 015import org.openstreetmap.josm.tools.MultiMap; 016 017public 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 the way to form the polygon 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 list of nodes 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 {@link #innerWays} and {@link #outerWays} to the result. 106 * TODO: Currently cannot process touching polygons. See code in JoinAreasAction. 107 * @param ways ways to analyze 108 * @return error description if the ways cannot be split, {@code null} if all fine. 109 */ 110 public String makeFromWays(Collection<Way> ways){ 111 List<JoinedPolygon> joinedWays = new ArrayList<JoinedPolygon>(); 112 113 //collect ways connecting to each node. 114 MultiMap<Node, Way> nodesWithConnectedWays = new MultiMap<Node, Way>(); 115 Set<Way> usedWays = new HashSet<Way>(); 116 117 for(Way w: ways) { 118 if (w.getNodesCount() < 2) { 119 return tr("Cannot add a way with only {0} nodes.", w.getNodesCount()); 120 } 121 122 if (w.isClosed()) { 123 //closed way, add as is. 124 JoinedPolygon jw = new JoinedPolygon(w); 125 joinedWays.add(jw); 126 usedWays.add(w); 127 } 128 else { 129 nodesWithConnectedWays.put(w.lastNode(), w); 130 nodesWithConnectedWays.put(w.firstNode(), w); 131 } 132 } 133 134 //process unclosed ways 135 for (Way startWay: ways) { 136 if (usedWays.contains(startWay)){ 137 continue; 138 } 139 140 Node startNode = startWay.firstNode(); 141 List<Way> collectedWays = new ArrayList<Way>(); 142 List<Boolean> collectedWaysReverse = new ArrayList<Boolean>(); 143 Way curWay = startWay; 144 Node prevNode = startNode; 145 146 //find polygon ways 147 while (true) { 148 boolean curWayReverse = prevNode == curWay.lastNode(); 149 Node nextNode = (curWayReverse) ? curWay.firstNode(): curWay.lastNode(); 150 151 //add cur way to the list 152 collectedWays.add(curWay); 153 collectedWaysReverse.add(Boolean.valueOf(curWayReverse)); 154 155 if (nextNode == startNode) { 156 //way finished 157 break; 158 } 159 160 //find next way 161 Collection<Way> adjacentWays = nodesWithConnectedWays.get(nextNode); 162 163 if (adjacentWays.size() != 2) { 164 return tr("Each node must connect exactly 2 ways"); 165 } 166 167 Way nextWay = null; 168 for(Way way: adjacentWays){ 169 if (way != curWay){ 170 nextWay = way; 171 } 172 } 173 174 //move to the next way 175 curWay = nextWay; 176 prevNode = nextNode; 177 } 178 179 usedWays.addAll(collectedWays); 180 joinedWays.add(new JoinedPolygon(collectedWays, collectedWaysReverse)); 181 } 182 183 //analyze witch way is inside witch outside. 184 return makeFromPolygons(joinedWays); 185 } 186 187 /** 188 * This method analyzes which ways are inner and which outer. Sets {@link #innerWays} and {@link #outerWays} to the result. 189 * @param polygons polygons to analyze 190 * @return error description if the ways cannot be split, {@code null} if all fine. 191 */ 192 private String makeFromPolygons(List<JoinedPolygon> polygons) { 193 List<PolygonLevel> list = findOuterWaysRecursive(0, polygons); 194 195 if (list == null){ 196 return tr("There is an intersection between ways."); 197 } 198 199 this.outerWays = new ArrayList<JoinedPolygon>(0); 200 this.innerWays = new ArrayList<JoinedPolygon>(0); 201 202 //take every other level 203 for (PolygonLevel pol : list) { 204 if (pol.level % 2 == 0) { 205 this.outerWays.add(pol.outerWay); 206 } 207 else { 208 this.innerWays.add(pol.outerWay); 209 } 210 } 211 212 return null; 213 } 214 215 /** 216 * Collects outer way and corresponding inner ways from all boundaries. 217 * @param boundaryWays 218 * @return the outermostWay, or {@code null} if intersection found. 219 */ 220 private List<PolygonLevel> findOuterWaysRecursive(int level, Collection<JoinedPolygon> boundaryWays) { 221 222 //TODO: bad performance for deep nesting... 223 List<PolygonLevel> result = new ArrayList<PolygonLevel>(); 224 225 for (JoinedPolygon outerWay : boundaryWays) { 226 227 boolean outerGood = true; 228 List<JoinedPolygon> innerCandidates = new ArrayList<JoinedPolygon>(); 229 230 for (JoinedPolygon innerWay : boundaryWays) { 231 if (innerWay == outerWay) { 232 continue; 233 } 234 235 PolygonIntersection intersection = Geometry.polygonIntersection(outerWay.nodes, innerWay.nodes); 236 237 if (intersection == PolygonIntersection.FIRST_INSIDE_SECOND) { 238 outerGood = false; // outer is inside another polygon 239 break; 240 } else if (intersection == PolygonIntersection.SECOND_INSIDE_FIRST) { 241 innerCandidates.add(innerWay); 242 } 243 else if (intersection == PolygonIntersection.CROSSING) 244 { 245 //ways intersect 246 return null; 247 } 248 } 249 250 if (!outerGood) { 251 continue; 252 } 253 254 //add new outer polygon 255 PolygonLevel pol = new PolygonLevel(outerWay, level); 256 257 //process inner ways 258 if (!innerCandidates.isEmpty()) { 259 List<PolygonLevel> innerList = this.findOuterWaysRecursive(level + 1, innerCandidates); 260 if (innerList == null) { 261 return null; //intersection found 262 } 263 264 result.addAll(innerList); 265 266 for (PolygonLevel pl : innerList) { 267 if (pl.level == level + 1) { 268 pol.innerWays.add(pl.outerWay); 269 } 270 } 271 } 272 273 result.add(pol); 274 } 275 276 return result; 277 } 278}