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.awt.geom.Area; 007import java.util.ArrayList; 008import java.util.Collection; 009import java.util.Collections; 010import java.util.HashSet; 011import java.util.List; 012import java.util.Set; 013 014import org.openstreetmap.josm.tools.Geometry; 015import org.openstreetmap.josm.tools.Geometry.PolygonIntersection; 016import org.openstreetmap.josm.tools.MultiMap; 017 018public class MultipolygonCreate { 019 020 /** 021 * Represents one polygon that consists of multiple ways. 022 * @author Viesturs 023 * 024 */ 025 public static class JoinedPolygon { 026 public final List<Way> ways; 027 public final List<Boolean> reversed; 028 public final List<Node> nodes; 029 public final Area area; 030 031 public JoinedPolygon(List<Way> ways, List<Boolean> reversed) { 032 this.ways = ways; 033 this.reversed = reversed; 034 this.nodes = this.getNodes(); 035 this.area = Geometry.getArea(nodes); 036 } 037 038 /** 039 * Creates a polygon from single way. 040 * @param way the way to form the polygon 041 */ 042 public JoinedPolygon(Way way) { 043 this(Collections.singletonList(way), Collections.singletonList(Boolean.FALSE)); 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 public List<Node> getNodes() { 051 List<Node> nodes = new ArrayList<>(); 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<>(); 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<>(0); 101 this.innerWays = new ArrayList<>(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 try { 112 List<JoinedPolygon> joinedWays = joinWays(ways); 113 //analyze witch way is inside witch outside. 114 return makeFromPolygons(joinedWays); 115 } catch (JoinedPolygonCreationException ex) { 116 return ex.getMessage(); 117 } 118 } 119 120 /** 121 * An exception indicating an error while joining ways to multipolygon rings. 122 */ 123 public static class JoinedPolygonCreationException extends RuntimeException { 124 public JoinedPolygonCreationException(String message) { 125 super(message); 126 } 127 } 128 129 /** 130 * Joins the given {@code ways} to multipolygon rings. 131 * @param ways the ways to join. 132 * @return a list of multipolygon rings. 133 * @throws JoinedPolygonCreationException if the creation fails. 134 */ 135 public static List<JoinedPolygon> joinWays(Collection<Way> ways) throws JoinedPolygonCreationException { 136 List<JoinedPolygon> joinedWays = new ArrayList<>(); 137 138 //collect ways connecting to each node. 139 MultiMap<Node, Way> nodesWithConnectedWays = new MultiMap<>(); 140 Set<Way> usedWays = new HashSet<>(); 141 142 for(Way w: ways) { 143 if (w.getNodesCount() < 2) { 144 throw new JoinedPolygonCreationException(tr("Cannot add a way with only {0} nodes.", w.getNodesCount())); 145 } 146 147 if (w.isClosed()) { 148 //closed way, add as is. 149 JoinedPolygon jw = new JoinedPolygon(w); 150 joinedWays.add(jw); 151 usedWays.add(w); 152 } 153 else { 154 nodesWithConnectedWays.put(w.lastNode(), w); 155 nodesWithConnectedWays.put(w.firstNode(), w); 156 } 157 } 158 159 //process unclosed ways 160 for (Way startWay: ways) { 161 if (usedWays.contains(startWay)){ 162 continue; 163 } 164 165 Node startNode = startWay.firstNode(); 166 List<Way> collectedWays = new ArrayList<>(); 167 List<Boolean> collectedWaysReverse = new ArrayList<>(); 168 Way curWay = startWay; 169 Node prevNode = startNode; 170 171 //find polygon ways 172 while (true) { 173 boolean curWayReverse = prevNode == curWay.lastNode(); 174 Node nextNode = (curWayReverse) ? curWay.firstNode(): curWay.lastNode(); 175 176 //add cur way to the list 177 collectedWays.add(curWay); 178 collectedWaysReverse.add(Boolean.valueOf(curWayReverse)); 179 180 if (nextNode == startNode) { 181 //way finished 182 break; 183 } 184 185 //find next way 186 Collection<Way> adjacentWays = nodesWithConnectedWays.get(nextNode); 187 188 if (adjacentWays.size() != 2) { 189 throw new JoinedPolygonCreationException(tr("Each node must connect exactly 2 ways")); 190 } 191 192 Way nextWay = null; 193 for(Way way: adjacentWays){ 194 if (way != curWay){ 195 nextWay = way; 196 } 197 } 198 199 //move to the next way 200 curWay = nextWay; 201 prevNode = nextNode; 202 } 203 204 usedWays.addAll(collectedWays); 205 joinedWays.add(new JoinedPolygon(collectedWays, collectedWaysReverse)); 206 } 207 208 return joinedWays; 209 } 210 211 /** 212 * This method analyzes which ways are inner and which outer. Sets {@link #innerWays} and {@link #outerWays} to the result. 213 * @param polygons polygons to analyze 214 * @return error description if the ways cannot be split, {@code null} if all fine. 215 */ 216 private String makeFromPolygons(List<JoinedPolygon> polygons) { 217 List<PolygonLevel> list = findOuterWaysRecursive(0, polygons); 218 219 if (list == null){ 220 return tr("There is an intersection between ways."); 221 } 222 223 this.outerWays = new ArrayList<>(0); 224 this.innerWays = new ArrayList<>(0); 225 226 //take every other level 227 for (PolygonLevel pol : list) { 228 if (pol.level % 2 == 0) { 229 this.outerWays.add(pol.outerWay); 230 } 231 else { 232 this.innerWays.add(pol.outerWay); 233 } 234 } 235 236 return null; 237 } 238 239 /** 240 * Collects outer way and corresponding inner ways from all boundaries. 241 * @param boundaryWays 242 * @return the outermostWay, or {@code null} if intersection found. 243 */ 244 private List<PolygonLevel> findOuterWaysRecursive(int level, Collection<JoinedPolygon> boundaryWays) { 245 246 //TODO: bad performance for deep nesting... 247 List<PolygonLevel> result = new ArrayList<>(); 248 249 for (JoinedPolygon outerWay : boundaryWays) { 250 251 boolean outerGood = true; 252 List<JoinedPolygon> innerCandidates = new ArrayList<>(); 253 254 for (JoinedPolygon innerWay : boundaryWays) { 255 if (innerWay == outerWay) { 256 continue; 257 } 258 259 PolygonIntersection intersection = Geometry.polygonIntersection(outerWay.area, innerWay.area); 260 261 if (intersection == PolygonIntersection.FIRST_INSIDE_SECOND) { 262 outerGood = false; // outer is inside another polygon 263 break; 264 } else if (intersection == PolygonIntersection.SECOND_INSIDE_FIRST) { 265 innerCandidates.add(innerWay); 266 } 267 else if (intersection == PolygonIntersection.CROSSING) 268 { 269 //ways intersect 270 return null; 271 } 272 } 273 274 if (!outerGood) { 275 continue; 276 } 277 278 //add new outer polygon 279 PolygonLevel pol = new PolygonLevel(outerWay, level); 280 281 //process inner ways 282 if (!innerCandidates.isEmpty()) { 283 List<PolygonLevel> innerList = this.findOuterWaysRecursive(level + 1, innerCandidates); 284 if (innerList == null) { 285 return null; //intersection found 286 } 287 288 result.addAll(innerList); 289 290 for (PolygonLevel pl : innerList) { 291 if (pl.level == level + 1) { 292 pol.innerWays.add(pl.outerWay); 293 } 294 } 295 } 296 297 result.add(pol); 298 } 299 300 return result; 301 } 302}