 Timestamp:
 20161011T21:09:53+02:00 (3 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/src/org/openstreetmap/josm/data/osm/MultipolygonBuilder.java
r10943 r11119 12 12 import java.util.Collection; 13 13 import java.util.Collections; 14 import java.util.HashMap; 14 15 import java.util.HashSet; 15 16 import java.util.List; … … 19 20 import java.util.concurrent.ForkJoinTask; 20 21 import java.util.concurrent.RecursiveTask; 22 import java.util.function.Supplier; 21 23 import java.util.stream.Collectors; 22 24 … … 39 41 private static final ForkJoinPool THREAD_POOL = 40 42 Utils.newForkJoinPool("multipolygon_creation.numberOfThreads", "multipolygonbuilder%d", Thread.NORM_PRIORITY); 43 44 /** 45 * Helper class to avoid unneeded costly intersection calculations. 46 * If the intersection between polygons a and b was calculated we also know 47 * the result of intersection between b and a. The lookup in the hash tables is 48 * much faster than the intersection calculation. 49 */ 50 private static class IntersectionMatrix { 51 private final Map<Pair<JoinedPolygon, JoinedPolygon>, PolygonIntersection> results; 52 53 IntersectionMatrix(Collection<JoinedPolygon> polygons) { 54 results = new HashMap<>(Utils.hashMapInitialCapacity(polygons.size() * polygons.size())); 55 } 56 57 /** 58 * Compute the reverse result of the intersection test done by {@code Geometry.polygonIntersection(Area a1, Area a2)} 59 * 60 * @param intersection the intersection result for polygons a1 and a2 (in that order) 61 * @return the intersection result for a2 and a1 62 */ 63 private PolygonIntersection getReverseIntersectionResult(PolygonIntersection intersection) { 64 switch (intersection) { 65 case FIRST_INSIDE_SECOND: 66 return PolygonIntersection.SECOND_INSIDE_FIRST; 67 case SECOND_INSIDE_FIRST: 68 return PolygonIntersection.FIRST_INSIDE_SECOND; 69 default: 70 return intersection; 71 } 72 } 73 74 /** 75 * Returns the precomputed intersection between two polygons if known. Otherwise perform {@code computation}. 76 * 77 * @param a1 first polygon 78 * @param a2 second polygon 79 * @param computation the computation to perform when intersection is unknown 80 * @return the intersection between two polygons 81 * @see Map#computeIfAbsent 82 */ 83 PolygonIntersection computeIfAbsent(JoinedPolygon a1, JoinedPolygon a2, Supplier<PolygonIntersection> computation) { 84 PolygonIntersection intersection = results.get(Pair.create(a1, a2)); 85 if (intersection == null) { 86 intersection = computation.get(); 87 synchronized (results) { 88 results.put(Pair.create(a1, a2), intersection); 89 results.put(Pair.create(a2, a1), getReverseIntersectionResult(intersection)); 90 } 91 } 92 return intersection; 93 } 94 95 } 41 96 42 97 /** … … 292 347 } 293 348 294 private static Pair<Boolean, List<JoinedPolygon>> findInnerWaysCandidates(JoinedPolygon outerWay, Collection<JoinedPolygon> boundaryWays) { 349 private static Pair<Boolean, List<JoinedPolygon>> findInnerWaysCandidates(IntersectionMatrix cache, 350 JoinedPolygon outerWay, Collection<JoinedPolygon> boundaryWays) { 295 351 boolean outerGood = true; 296 352 List<JoinedPolygon> innerCandidates = new ArrayList<>(); … … 304 360 if (outerWay.bounds.intersects(innerWay.bounds)) { 305 361 // Bounds intersection, let's see in detail 306 PolygonIntersection intersection = Geometry.polygonIntersection(outerWay.area, innerWay.area); 362 final PolygonIntersection intersection = cache.computeIfAbsent(outerWay, innerWay, 363 () > Geometry.polygonIntersection(outerWay.area, innerWay.area)); 307 364 308 365 if (intersection == PolygonIntersection.FIRST_INSIDE_SECOND) { … … 327 384 */ 328 385 private static List<PolygonLevel> findOuterWaysMultiThread(List<JoinedPolygon> boundaryWays) { 329 return THREAD_POOL.invoke(new Worker(boundaryWays, 0, boundaryWays.size(), new ArrayList<PolygonLevel>(), 386 final IntersectionMatrix cache = new IntersectionMatrix(boundaryWays); 387 return THREAD_POOL.invoke(new Worker(cache, boundaryWays, 0, boundaryWays.size(), new ArrayList<PolygonLevel>(), 330 388 Math.max(32, boundaryWays.size() / THREAD_POOL.getParallelism() / 3))); 331 389 } … … 341 399 private final transient List<PolygonLevel> output; 342 400 private final int directExecutionTaskSize; 343 344 Worker(List<JoinedPolygon> input, int from, int to, List<PolygonLevel> output, 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; 345 405 this.input = input; 346 406 this.from = from; … … 353 413 * Collects outer way and corresponding inner ways from all boundaries. 354 414 * @param level nesting level 415 * @param cache cache that tracks previously calculated results 355 416 * @param boundaryWays boundary ways 356 417 * @return the outermostWay, or {@code null} if intersection found. 357 418 */ 358 private static List<PolygonLevel> findOuterWaysRecursive(int level, List<JoinedPolygon> boundaryWays) {419 private static List<PolygonLevel> findOuterWaysRecursive(int level, IntersectionMatrix cache, List<JoinedPolygon> boundaryWays) { 359 420 360 421 final List<PolygonLevel> result = new ArrayList<>(); 361 422 362 423 for (JoinedPolygon outerWay : boundaryWays) { 363 if (processOuterWay(level, boundaryWays, result, outerWay) == null) {424 if (processOuterWay(level, cache, boundaryWays, result, outerWay) == null) { 364 425 return null; 365 426 } … … 369 430 } 370 431 371 private static List<PolygonLevel> processOuterWay(int level, List<JoinedPolygon> boundaryWays,432 private static List<PolygonLevel> processOuterWay(int level, IntersectionMatrix cache, List<JoinedPolygon> boundaryWays, 372 433 final List<PolygonLevel> result, JoinedPolygon outerWay) { 373 Pair<Boolean, List<JoinedPolygon>> p = findInnerWaysCandidates( outerWay, boundaryWays);434 Pair<Boolean, List<JoinedPolygon>> p = findInnerWaysCandidates(cache, outerWay, boundaryWays); 374 435 if (p == null) { 375 436 // ways intersect … … 383 444 //process inner ways 384 445 if (!p.b.isEmpty()) { 385 List<PolygonLevel> innerList = findOuterWaysRecursive(level + 1, p.b);446 List<PolygonLevel> innerList = findOuterWaysRecursive(level + 1, cache, p.b); 386 447 if (innerList == null) { 387 448 return null; //intersection found … … 409 470 final Collection<ForkJoinTask<List<PolygonLevel>>> tasks = new ArrayList<>(); 410 471 for (int fromIndex = from; fromIndex < to; fromIndex += directExecutionTaskSize) { 411 tasks.add(new Worker( input, fromIndex, Math.min(fromIndex + directExecutionTaskSize, to),472 tasks.add(new Worker(cache, input, fromIndex, Math.min(fromIndex + directExecutionTaskSize, to), 412 473 new ArrayList<PolygonLevel>(), directExecutionTaskSize)); 413 474 } … … 425 486 List<PolygonLevel> computeDirectly() { 426 487 for (int i = from; i < to; i++) { 427 if (processOuterWay(0, input, output, input.get(i)) == null) {488 if (processOuterWay(0, cache, input, output, input.get(i)) == null) { 428 489 return null; 429 490 }
Note: See TracChangeset
for help on using the changeset viewer.