Ignore:
Timestamp:
2016-10-11T21:09:53+02:00 (8 years ago)
Author:
simon04
Message:

fix #13289 - Cache polygonIntersection results in MultipolygonBuilder (patch by Gerd Petermann, modified)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/org/openstreetmap/josm/data/osm/MultipolygonBuilder.java

    r10943 r11119  
    1212import java.util.Collection;
    1313import java.util.Collections;
     14import java.util.HashMap;
    1415import java.util.HashSet;
    1516import java.util.List;
     
    1920import java.util.concurrent.ForkJoinTask;
    2021import java.util.concurrent.RecursiveTask;
     22import java.util.function.Supplier;
    2123import java.util.stream.Collectors;
    2224
     
    3941    private static final ForkJoinPool THREAD_POOL =
    4042            Utils.newForkJoinPool("multipolygon_creation.numberOfThreads", "multipolygon-builder-%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    }
    4196
    4297    /**
     
    292347    }
    293348
    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) {
    295351        boolean outerGood = true;
    296352        List<JoinedPolygon> innerCandidates = new ArrayList<>();
     
    304360            if (outerWay.bounds.intersects(innerWay.bounds)) {
    305361                // 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));
    307364
    308365                if (intersection == PolygonIntersection.FIRST_INSIDE_SECOND) {
     
    327384     */
    328385    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>(),
    330388                Math.max(32, boundaryWays.size() / THREAD_POOL.getParallelism() / 3)));
    331389    }
     
    341399        private final transient List<PolygonLevel> output;
    342400        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;
    345405            this.input = input;
    346406            this.from = from;
     
    353413         * Collects outer way and corresponding inner ways from all boundaries.
    354414         * @param level nesting level
     415         * @param cache cache that tracks previously calculated results
    355416         * @param boundaryWays boundary ways
    356417         * @return the outermostWay, or {@code null} if intersection found.
    357418         */
    358         private static List<PolygonLevel> findOuterWaysRecursive(int level, List<JoinedPolygon> boundaryWays) {
     419        private static List<PolygonLevel> findOuterWaysRecursive(int level, IntersectionMatrix cache, List<JoinedPolygon> boundaryWays) {
    359420
    360421            final List<PolygonLevel> result = new ArrayList<>();
    361422
    362423            for (JoinedPolygon outerWay : boundaryWays) {
    363                 if (processOuterWay(level, boundaryWays, result, outerWay) == null) {
     424                if (processOuterWay(level, cache, boundaryWays, result, outerWay) == null) {
    364425                    return null;
    365426                }
     
    369430        }
    370431
    371         private static List<PolygonLevel> processOuterWay(int level, List<JoinedPolygon> boundaryWays,
     432        private static List<PolygonLevel> processOuterWay(int level, IntersectionMatrix cache, List<JoinedPolygon> boundaryWays,
    372433                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);
    374435            if (p == null) {
    375436                // ways intersect
     
    383444                //process inner ways
    384445                if (!p.b.isEmpty()) {
    385                     List<PolygonLevel> innerList = findOuterWaysRecursive(level + 1, p.b);
     446                    List<PolygonLevel> innerList = findOuterWaysRecursive(level + 1, cache, p.b);
    386447                    if (innerList == null) {
    387448                        return null; //intersection found
     
    409470                final Collection<ForkJoinTask<List<PolygonLevel>>> tasks = new ArrayList<>();
    410471                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),
    412473                            new ArrayList<PolygonLevel>(), directExecutionTaskSize));
    413474                }
     
    425486        List<PolygonLevel> computeDirectly() {
    426487            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) {
    428489                    return null;
    429490                }
Note: See TracChangeset for help on using the changeset viewer.