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.Rectangle; 007import java.awt.geom.Area; 008import java.io.IOException; 009import java.io.ObjectInputStream; 010import java.io.ObjectOutputStream; 011import java.util.ArrayList; 012import java.util.Collection; 013import java.util.Collections; 014import java.util.HashSet; 015import java.util.List; 016import java.util.Set; 017import java.util.concurrent.ForkJoinPool; 018import java.util.concurrent.ForkJoinTask; 019import java.util.concurrent.RecursiveTask; 020 021import org.openstreetmap.josm.Main; 022import org.openstreetmap.josm.tools.Geometry; 023import org.openstreetmap.josm.tools.Geometry.PolygonIntersection; 024import org.openstreetmap.josm.tools.MultiMap; 025import org.openstreetmap.josm.tools.Pair; 026import org.openstreetmap.josm.tools.Utils; 027 028/** 029 * Helper class to build multipolygons from multiple ways. 030 * @author viesturs 031 * @since 7392 (rename) 032 * @since 3704 033 */ 034public class MultipolygonBuilder { 035 036 private static final ForkJoinPool THREAD_POOL = 037 Utils.newForkJoinPool("multipolygon_creation.numberOfThreads", "multipolygon-builder-%d", Thread.NORM_PRIORITY); 038 039 /** 040 * Represents one polygon that consists of multiple ways. 041 */ 042 public static class JoinedPolygon { 043 public final List<Way> ways; 044 public final List<Boolean> reversed; 045 public final List<Node> nodes; 046 public final Area area; 047 public final Rectangle bounds; 048 049 /** 050 * Constructs a new {@code JoinedPolygon} from given list of ways. 051 * @param ways The ways used to build joined polygon 052 * @param reversed list of reversed states 053 */ 054 public JoinedPolygon(List<Way> ways, List<Boolean> reversed) { 055 this.ways = ways; 056 this.reversed = reversed; 057 this.nodes = this.getNodes(); 058 this.area = Geometry.getArea(nodes); 059 this.bounds = area.getBounds(); 060 } 061 062 /** 063 * Creates a polygon from single way. 064 * @param way the way to form the polygon 065 */ 066 public JoinedPolygon(Way way) { 067 this(Collections.singletonList(way), Collections.singletonList(Boolean.FALSE)); 068 } 069 070 /** 071 * Builds a list of nodes for this polygon. First node is not duplicated as last node. 072 * @return list of nodes 073 */ 074 public List<Node> getNodes() { 075 List<Node> nodes = new ArrayList<>(); 076 077 for (int waypos = 0; waypos < this.ways.size(); waypos++) { 078 Way way = this.ways.get(waypos); 079 boolean reversed = this.reversed.get(waypos).booleanValue(); 080 081 if (!reversed) { 082 for (int pos = 0; pos < way.getNodesCount() - 1; pos++) { 083 nodes.add(way.getNode(pos)); 084 } 085 } else { 086 for (int pos = way.getNodesCount() - 1; pos > 0; pos--) { 087 nodes.add(way.getNode(pos)); 088 } 089 } 090 } 091 092 return nodes; 093 } 094 } 095 096 /** 097 * Helper storage class for finding findOuterWays 098 */ 099 static class PolygonLevel { 100 public final int level; // nesting level, even for outer, odd for inner polygons. 101 public final JoinedPolygon outerWay; 102 103 public List<JoinedPolygon> innerWays; 104 105 PolygonLevel(JoinedPolygon pol, int level) { 106 this.outerWay = pol; 107 this.level = level; 108 this.innerWays = new ArrayList<>(); 109 } 110 } 111 112 /** List of outer ways **/ 113 public final List<JoinedPolygon> outerWays; 114 /** List of inner ways **/ 115 public final List<JoinedPolygon> innerWays; 116 117 /** 118 * Constructs a new {@code MultipolygonBuilder} initialized with given ways. 119 * @param outerWays The outer ways 120 * @param innerWays The inner ways 121 */ 122 public MultipolygonBuilder(List<JoinedPolygon> outerWays, List<JoinedPolygon> innerWays) { 123 this.outerWays = outerWays; 124 this.innerWays = innerWays; 125 } 126 127 /** 128 * Constructs a new empty {@code MultipolygonBuilder}. 129 */ 130 public MultipolygonBuilder() { 131 this.outerWays = new ArrayList<>(0); 132 this.innerWays = new ArrayList<>(0); 133 } 134 135 /** 136 * Splits ways into inner and outer JoinedWays. Sets {@link #innerWays} and {@link #outerWays} to the result. 137 * TODO: Currently cannot process touching polygons. See code in JoinAreasAction. 138 * @param ways ways to analyze 139 * @return error description if the ways cannot be split, {@code null} if all fine. 140 */ 141 public String makeFromWays(Collection<Way> ways) { 142 try { 143 List<JoinedPolygon> joinedWays = joinWays(ways); 144 //analyze witch way is inside witch outside. 145 return makeFromPolygons(joinedWays); 146 } catch (JoinedPolygonCreationException ex) { 147 Main.debug(ex); 148 return ex.getMessage(); 149 } 150 } 151 152 /** 153 * An exception indicating an error while joining ways to multipolygon rings. 154 */ 155 public static class JoinedPolygonCreationException extends RuntimeException { 156 /** 157 * Constructs a new {@code JoinedPolygonCreationException}. 158 * @param message the detail message. The detail message is saved for 159 * later retrieval by the {@link #getMessage()} method 160 */ 161 public JoinedPolygonCreationException(String message) { 162 super(message); 163 } 164 } 165 166 /** 167 * Joins the given {@code ways} to multipolygon rings. 168 * @param ways the ways to join. 169 * @return a list of multipolygon rings. 170 * @throws JoinedPolygonCreationException if the creation fails. 171 */ 172 public static List<JoinedPolygon> joinWays(Collection<Way> ways) throws JoinedPolygonCreationException { 173 List<JoinedPolygon> joinedWays = new ArrayList<>(); 174 175 //collect ways connecting to each node. 176 MultiMap<Node, Way> nodesWithConnectedWays = new MultiMap<>(); 177 Set<Way> usedWays = new HashSet<>(); 178 179 for (Way w: ways) { 180 if (w.getNodesCount() < 2) { 181 throw new JoinedPolygonCreationException(tr("Cannot add a way with only {0} nodes.", w.getNodesCount())); 182 } 183 184 if (w.isClosed()) { 185 //closed way, add as is. 186 JoinedPolygon jw = new JoinedPolygon(w); 187 joinedWays.add(jw); 188 usedWays.add(w); 189 } else { 190 nodesWithConnectedWays.put(w.lastNode(), w); 191 nodesWithConnectedWays.put(w.firstNode(), w); 192 } 193 } 194 195 //process unclosed ways 196 for (Way startWay: ways) { 197 if (usedWays.contains(startWay)) { 198 continue; 199 } 200 201 Node startNode = startWay.firstNode(); 202 List<Way> collectedWays = new ArrayList<>(); 203 List<Boolean> collectedWaysReverse = new ArrayList<>(); 204 Way curWay = startWay; 205 Node prevNode = startNode; 206 207 //find polygon ways 208 while (true) { 209 boolean curWayReverse = prevNode == curWay.lastNode(); 210 Node nextNode = curWayReverse ? curWay.firstNode() : curWay.lastNode(); 211 212 //add cur way to the list 213 collectedWays.add(curWay); 214 collectedWaysReverse.add(Boolean.valueOf(curWayReverse)); 215 216 if (nextNode == startNode) { 217 //way finished 218 break; 219 } 220 221 //find next way 222 Collection<Way> adjacentWays = nodesWithConnectedWays.get(nextNode); 223 224 if (adjacentWays.size() != 2) { 225 throw new JoinedPolygonCreationException(tr("Each node must connect exactly 2 ways")); 226 } 227 228 Way nextWay = null; 229 for (Way way: adjacentWays) { 230 if (way != curWay) { 231 nextWay = way; 232 } 233 } 234 235 //move to the next way 236 curWay = nextWay; 237 prevNode = nextNode; 238 } 239 240 usedWays.addAll(collectedWays); 241 joinedWays.add(new JoinedPolygon(collectedWays, collectedWaysReverse)); 242 } 243 244 return joinedWays; 245 } 246 247 /** 248 * This method analyzes which ways are inner and which outer. Sets {@link #innerWays} and {@link #outerWays} to the result. 249 * @param polygons polygons to analyze 250 * @return error description if the ways cannot be split, {@code null} if all fine. 251 */ 252 private String makeFromPolygons(List<JoinedPolygon> polygons) { 253 List<PolygonLevel> list = findOuterWaysMultiThread(polygons); 254 255 if (list == null) { 256 return tr("There is an intersection between ways."); 257 } 258 259 this.outerWays.clear(); 260 this.innerWays.clear(); 261 262 //take every other level 263 for (PolygonLevel pol : list) { 264 if (pol.level % 2 == 0) { 265 this.outerWays.add(pol.outerWay); 266 } else { 267 this.innerWays.add(pol.outerWay); 268 } 269 } 270 271 return null; 272 } 273 274 private static Pair<Boolean, List<JoinedPolygon>> findInnerWaysCandidates(JoinedPolygon outerWay, Collection<JoinedPolygon> boundaryWays) { 275 boolean outerGood = true; 276 List<JoinedPolygon> innerCandidates = new ArrayList<>(); 277 278 for (JoinedPolygon innerWay : boundaryWays) { 279 if (innerWay == outerWay) { 280 continue; 281 } 282 283 // Preliminary computation on bounds. If bounds do not intersect, no need to do a costly area intersection 284 if (outerWay.bounds.intersects(innerWay.bounds)) { 285 // Bounds intersection, let's see in detail 286 PolygonIntersection intersection = Geometry.polygonIntersection(outerWay.area, innerWay.area); 287 288 if (intersection == PolygonIntersection.FIRST_INSIDE_SECOND) { 289 outerGood = false; // outer is inside another polygon 290 break; 291 } else if (intersection == PolygonIntersection.SECOND_INSIDE_FIRST) { 292 innerCandidates.add(innerWay); 293 } else if (intersection == PolygonIntersection.CROSSING) { 294 // ways intersect 295 return null; 296 } 297 } 298 } 299 300 return new Pair<>(outerGood, innerCandidates); 301 } 302 303 /** 304 * Collects outer way and corresponding inner ways from all boundaries. 305 * @param boundaryWays boundary ways 306 * @return the outermostWay, or {@code null} if intersection found. 307 */ 308 private static List<PolygonLevel> findOuterWaysMultiThread(List<JoinedPolygon> boundaryWays) { 309 return THREAD_POOL.invoke(new Worker(boundaryWays, 0, boundaryWays.size(), new ArrayList<PolygonLevel>(), 310 Math.max(32, boundaryWays.size() / THREAD_POOL.getParallelism() / 3))); 311 } 312 313 private static class Worker extends RecursiveTask<List<PolygonLevel>> { 314 315 // Needed for Findbugs / Coverity because parent class is serializable 316 private static final long serialVersionUID = 1L; 317 318 private final transient List<JoinedPolygon> input; 319 private final int from; 320 private final int to; 321 private final transient List<PolygonLevel> output; 322 private final int directExecutionTaskSize; 323 324 Worker(List<JoinedPolygon> input, int from, int to, List<PolygonLevel> output, int directExecutionTaskSize) { 325 this.input = input; 326 this.from = from; 327 this.to = to; 328 this.output = output; 329 this.directExecutionTaskSize = directExecutionTaskSize; 330 } 331 332 /** 333 * Collects outer way and corresponding inner ways from all boundaries. 334 * @param level nesting level 335 * @param boundaryWays boundary ways 336 * @return the outermostWay, or {@code null} if intersection found. 337 */ 338 private static List<PolygonLevel> findOuterWaysRecursive(int level, List<JoinedPolygon> boundaryWays) { 339 340 final List<PolygonLevel> result = new ArrayList<>(); 341 342 for (JoinedPolygon outerWay : boundaryWays) { 343 if (processOuterWay(level, boundaryWays, result, outerWay) == null) { 344 return null; 345 } 346 } 347 348 return result; 349 } 350 351 private static List<PolygonLevel> processOuterWay(int level, List<JoinedPolygon> boundaryWays, 352 final List<PolygonLevel> result, JoinedPolygon outerWay) { 353 Pair<Boolean, List<JoinedPolygon>> p = findInnerWaysCandidates(outerWay, boundaryWays); 354 if (p == null) { 355 // ways intersect 356 return null; 357 } 358 359 if (p.a) { 360 //add new outer polygon 361 PolygonLevel pol = new PolygonLevel(outerWay, level); 362 363 //process inner ways 364 if (!p.b.isEmpty()) { 365 List<PolygonLevel> innerList = findOuterWaysRecursive(level + 1, p.b); 366 if (innerList == null) { 367 return null; //intersection found 368 } 369 370 result.addAll(innerList); 371 372 for (PolygonLevel pl : innerList) { 373 if (pl.level == level + 1) { 374 pol.innerWays.add(pl.outerWay); 375 } 376 } 377 } 378 379 result.add(pol); 380 } 381 return result; 382 } 383 384 @Override 385 protected List<PolygonLevel> compute() { 386 if (to - from <= directExecutionTaskSize) { 387 return computeDirectly(); 388 } else { 389 final Collection<ForkJoinTask<List<PolygonLevel>>> tasks = new ArrayList<>(); 390 for (int fromIndex = from; fromIndex < to; fromIndex += directExecutionTaskSize) { 391 tasks.add(new Worker(input, fromIndex, Math.min(fromIndex + directExecutionTaskSize, to), 392 new ArrayList<PolygonLevel>(), directExecutionTaskSize)); 393 } 394 for (ForkJoinTask<List<PolygonLevel>> task : ForkJoinTask.invokeAll(tasks)) { 395 List<PolygonLevel> res = task.join(); 396 if (res == null) { 397 return null; 398 } 399 output.addAll(res); 400 } 401 return output; 402 } 403 } 404 405 List<PolygonLevel> computeDirectly() { 406 for (int i = from; i < to; i++) { 407 if (processOuterWay(0, input, output, input.get(i)) == null) { 408 return null; 409 } 410 } 411 return output; 412 } 413 414 private void readObject(ObjectInputStream ois) throws ClassNotFoundException, IOException { 415 // Needed for Findbugs / Coverity because parent class is serializable 416 ois.defaultReadObject(); 417 } 418 419 private void writeObject(ObjectOutputStream oos) throws IOException { 420 // Needed for Findbugs / Coverity because parent class is serializable 421 oos.defaultWriteObject(); 422 } 423 } 424}