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