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