Changeset 7423 in josm for trunk/src


Ignore:
Timestamp:
2014-08-16T20:14:24+02:00 (5 years ago)
Author:
Don-vip
Message:

see #9680, see #4626 - multithreaded multipolygon creation

Location:
trunk/src/org/openstreetmap/josm
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/org/openstreetmap/josm/actions/CreateMultipolygonAction.java

    r7392 r7423  
    4343 * Create multipolygon from selected ways automatically.
    4444 *
    45  * New relation with type=multipolygon is created
     45 * New relation with type=multipolygon is created.
    4646 *
    4747 * If one or more of ways is already in relation with type=multipolygon or the
    48  * way is not closed, then error is reported and no relation is created
     48 * way is not closed, then error is reported and no relation is created.
    4949 *
    5050 * The "inner" and "outer" roles are guessed automatically. First, bbox is
     
    9393            final Relation relation = commandAndRelation.b;
    9494
    95 
    9695            // to avoid EDT violations
    9796            SwingUtilities.invokeLater(new Runnable() {
     
    103102                    // knows about the new relation before we try to select it.
    104103                    // (Yes, we are already in event dispatch thread. But DatasetEventManager
    105                     // uses 'SwingUtilities.invokeLater' to fire events so we have to do
    106                     // the same.)
     104                    // uses 'SwingUtilities.invokeLater' to fire events so we have to do the same.)
    107105                    SwingUtilities.invokeLater(new Runnable() {
    108106                        @Override
     
    123121    }
    124122
    125     /**
    126      * The action button has been clicked
    127      *
    128      * @param e Action Event
    129      */
    130123    @Override
    131124    public void actionPerformed(ActionEvent e) {
     
    239232
    240233    /** Enable this action only if something is selected */
    241     @Override protected void updateEnabledState() {
     234    @Override
     235    protected void updateEnabledState() {
    242236        if (getCurrentDataSet() == null) {
    243237            setEnabled(false);
     
    252246      * @param selection the current selection, gets tested for emptyness
    253247      */
    254     @Override protected void updateEnabledState(Collection < ? extends OsmPrimitive > selection) {
     248    @Override
     249    protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
    255250        if (update) {
    256251            setEnabled(getSelectedMultipolygonRelation() != null);
     
    265260     * @return <code>null</code>, if there was a problem with the ways.
    266261     */
    267     private static MultipolygonBuilder analyzeWays(Collection < Way > selectedWays, boolean showNotif) {
     262    private static MultipolygonBuilder analyzeWays(Collection<Way> selectedWays, boolean showNotif) {
    268263
    269264        MultipolygonBuilder pol = new MultipolygonBuilder();
     
    324319     * @return a list of commands to execute
    325320     */
    326     public static List<Command> removeTagsFromWaysIfNeeded( Relation relation ) {
     321    public static List<Command> removeTagsFromWaysIfNeeded(Relation relation) {
    327322        Map<String, String> values = new HashMap<>(relation.getKeys());
    328323
     
    342337                outerWays.add(way);
    343338
    344                 for( String key : way.keySet() ) {
    345                     if( !values.containsKey(key) ) { //relation values take precedence
     339                for (String key : way.keySet()) {
     340                    if (!values.containsKey(key)) { //relation values take precedence
    346341                        values.put(key, way.get(key));
    347                     } else if( !relation.hasKey(key) && !values.get(key).equals(way.get(key)) ) {
     342                    } else if (!relation.hasKey(key) && !values.get(key).equals(way.get(key))) {
    348343                        conflictingKeys.add(key);
    349344                    }
     
    353348
    354349        // filter out empty key conflicts - we need second iteration
    355         if( !Main.pref.getBoolean("multipoly.alltags", false) )
    356             for( RelationMember m : relation.getMembers() )
    357                 if( m.hasRole() && "outer".equals(m.getRole()) && m.isWay() )
    358                     for( String key : values.keySet() )
    359                         if( !m.getWay().hasKey(key) && !relation.hasKey(key) )
     350        if (!Main.pref.getBoolean("multipoly.alltags", false))
     351            for (RelationMember m : relation.getMembers())
     352                if (m.hasRole() && "outer".equals(m.getRole()) && m.isWay())
     353                    for (String key : values.keySet())
     354                        if (!m.getWay().hasKey(key) && !relation.hasKey(key))
    360355                            conflictingKeys.add(key);
    361356
    362         for( String key : conflictingKeys )
     357        for (String key : conflictingKeys)
    363358            values.remove(key);
    364359
    365         for( String linearTag : Main.pref.getCollection("multipoly.lineartagstokeep", DEFAULT_LINEAR_TAGS) )
     360        for (String linearTag : Main.pref.getCollection("multipoly.lineartagstokeep", DEFAULT_LINEAR_TAGS))
    366361            values.remove(linearTag);
    367362
     
    402397        if (moveTags) {
    403398            // add those tag values to the relation
    404 
    405399            boolean fixed = false;
    406400            Relation r2 = new Relation(relation);
  • trunk/src/org/openstreetmap/josm/data/osm/MultipolygonBuilder.java

    r7422 r7423  
    1212import java.util.List;
    1313import java.util.Set;
     14import java.util.concurrent.Callable;
     15import java.util.concurrent.ExecutionException;
     16import java.util.concurrent.ExecutorService;
     17import java.util.concurrent.Future;
    1418
    1519import org.openstreetmap.josm.tools.Geometry;
    1620import org.openstreetmap.josm.tools.Geometry.PolygonIntersection;
    1721import org.openstreetmap.josm.tools.MultiMap;
     22import org.openstreetmap.josm.tools.Pair;
     23import org.openstreetmap.josm.tools.Utils;
    1824
    1925/**
     
    2430 */
    2531public class MultipolygonBuilder {
     32
     33    private static final Pair<Integer, ExecutorService> THREAD_POOL =
     34            Utils.newThreadPool("multipolygon_creation.numberOfThreads");
    2635
    2736    /**
     
    237246     */
    238247    private String makeFromPolygons(List<JoinedPolygon> polygons) {
    239         List<PolygonLevel> list = findOuterWaysRecursive(0, polygons);
     248        List<PolygonLevel> list = findOuterWaysMultiThread(polygons);
    240249
    241250        if (list == null) {
     
    258267    }
    259268
     269    private static Pair<Boolean, List<JoinedPolygon>> findInnerWaysCandidates(JoinedPolygon outerWay, Collection<JoinedPolygon> boundaryWays) {
     270        boolean outerGood = true;
     271        List<JoinedPolygon> innerCandidates = new ArrayList<>();
     272
     273        for (JoinedPolygon innerWay : boundaryWays) {
     274            if (innerWay == outerWay) {
     275                continue;
     276            }
     277
     278            // Preliminary computation on bounds. If bounds do not intersect, no need to do a costly area intersection
     279            if (outerWay.bounds.intersects(innerWay.bounds)) {
     280                // Bounds intersection, let's see in detail
     281                PolygonIntersection intersection = Geometry.polygonIntersection(outerWay.area, innerWay.area);
     282
     283                if (intersection == PolygonIntersection.FIRST_INSIDE_SECOND) {
     284                    outerGood = false;  // outer is inside another polygon
     285                    break;
     286                } else if (intersection == PolygonIntersection.SECOND_INSIDE_FIRST) {
     287                    innerCandidates.add(innerWay);
     288                } else if (intersection == PolygonIntersection.CROSSING) {
     289                    // ways intersect
     290                    return null;
     291                }
     292            }
     293        }
     294
     295        return new Pair<>(outerGood, innerCandidates);
     296    }
     297
    260298    /**
    261299     * Collects outer way and corresponding inner ways from all boundaries.
    262      * @param boundaryWays
    263300     * @return the outermostWay, or {@code null} if intersection found.
    264301     */
    265     private List<PolygonLevel> findOuterWaysRecursive(int level, Collection<JoinedPolygon> boundaryWays) {
    266 
    267         //TODO: bad performance for deep nesting...
    268         List<PolygonLevel> result = new ArrayList<>();
    269 
    270         for (JoinedPolygon outerWay : boundaryWays) {
    271 
    272             boolean outerGood = true;
    273             List<JoinedPolygon> innerCandidates = new ArrayList<>();
    274 
    275             for (JoinedPolygon innerWay : boundaryWays) {
    276                 if (innerWay == outerWay) {
    277                     continue;
    278                 }
    279 
    280                 // Preliminary computation on bounds. If bounds do not intersect, no need to do a costly area intersection
    281                 if (outerWay.bounds.intersects(innerWay.bounds)) {
    282                     // Bounds intersection, let's see in detail
    283                     PolygonIntersection intersection = Geometry.polygonIntersection(outerWay.area, innerWay.area);
    284 
    285                     if (intersection == PolygonIntersection.FIRST_INSIDE_SECOND) {
    286                         outerGood = false;  // outer is inside another polygon
    287                         break;
    288                     } else if (intersection == PolygonIntersection.SECOND_INSIDE_FIRST) {
    289                         innerCandidates.add(innerWay);
    290                     } else if (intersection == PolygonIntersection.CROSSING) {
    291                         //ways intersect
     302    private static List<PolygonLevel> findOuterWaysMultiThread(List<JoinedPolygon> boundaryWays) {
     303        final List<PolygonLevel> result = new ArrayList<>();
     304        final List<Worker> tasks = new ArrayList<>();
     305        final int bucketsize = Math.max(32, boundaryWays.size()/THREAD_POOL.a/3);
     306        final int noBuckets = (boundaryWays.size() + bucketsize - 1) / bucketsize;
     307        final boolean singleThread = THREAD_POOL.a == 1 || noBuckets == 1;
     308        for (int i=0; i<noBuckets; i++) {
     309            int from = i*bucketsize;
     310            int to = Math.min((i+1)*bucketsize, boundaryWays.size());
     311            List<PolygonLevel> target = singleThread ? result : new ArrayList<PolygonLevel>(to - from);
     312            tasks.add(new Worker(boundaryWays, from, to, target));
     313        }
     314        if (singleThread) {
     315            try {
     316                for (Worker task : tasks) {
     317                    if (task.call() == null) {
    292318                        return null;
    293319                    }
    294320                }
    295             }
    296 
    297             if (!outerGood) {
    298                 continue;
    299             }
    300 
    301             //add new outer polygon
    302             PolygonLevel pol = new PolygonLevel(outerWay, level);
    303 
    304             //process inner ways
    305             if (!innerCandidates.isEmpty()) {
    306                 List<PolygonLevel> innerList = this.findOuterWaysRecursive(level + 1, innerCandidates);
    307                 if (innerList == null) {
    308                     return null; //intersection found
    309                 }
    310 
    311                 result.addAll(innerList);
    312 
    313                 for (PolygonLevel pl : innerList) {
    314                     if (pl.level == level + 1) {
    315                         pol.innerWays.add(pl.outerWay);
    316                     }
    317                 }
    318             }
    319 
    320             result.add(pol);
    321         }
    322 
     321            } catch (Exception ex) {
     322                throw new RuntimeException(ex);
     323            }
     324        } else if (!tasks.isEmpty()) {
     325            try {
     326                for (Future<List<PolygonLevel>> future : THREAD_POOL.b.invokeAll(tasks)) {
     327                    List<PolygonLevel> res = future.get();
     328                    if (res == null) {
     329                        return null;
     330                    }
     331                    result.addAll(res);
     332                }
     333            } catch (InterruptedException | ExecutionException ex) {
     334                throw new RuntimeException(ex);
     335            }
     336        }
    323337        return result;
    324338    }
     339
     340    private static class Worker implements Callable<List<PolygonLevel>> {
     341
     342        private final List<JoinedPolygon> input;
     343        private final int from;
     344        private final int to;
     345        private final List<PolygonLevel> output;
     346
     347        public Worker(List<JoinedPolygon> input, int from, int to, List<PolygonLevel> output) {
     348            this.input = input;
     349            this.from = from;
     350            this.to = to;
     351            this.output = output;
     352        }
     353
     354        /**
     355         * Collects outer way and corresponding inner ways from all boundaries.
     356         * @return the outermostWay, or {@code null} if intersection found.
     357         */
     358        private static List<PolygonLevel> findOuterWaysRecursive(int level, List<JoinedPolygon> boundaryWays) {
     359
     360            final List<PolygonLevel> result = new ArrayList<>();
     361
     362            for (JoinedPolygon outerWay : boundaryWays) {
     363                if (processOuterWay(level, boundaryWays, result, outerWay) == null) {
     364                    return null;
     365                }
     366            }
     367
     368            return result;
     369        }
     370
     371        private static List<PolygonLevel> processOuterWay(int level, List<JoinedPolygon> boundaryWays, final List<PolygonLevel> result, JoinedPolygon outerWay) {
     372            Pair<Boolean, List<JoinedPolygon>> p = findInnerWaysCandidates(outerWay, boundaryWays);
     373            if (p == null) {
     374                // ways intersect
     375                return null;
     376            }
     377
     378            if (p.a) {
     379                //add new outer polygon
     380                PolygonLevel pol = new PolygonLevel(outerWay, level);
     381
     382                //process inner ways
     383                if (!p.b.isEmpty()) {
     384                    List<PolygonLevel> innerList = findOuterWaysRecursive(level + 1, p.b);
     385                    if (innerList == null) {
     386                        return null; //intersection found
     387                    }
     388
     389                    result.addAll(innerList);
     390
     391                    for (PolygonLevel pl : innerList) {
     392                        if (pl.level == level + 1) {
     393                            pol.innerWays.add(pl.outerWay);
     394                        }
     395                    }
     396                }
     397
     398                result.add(pol);
     399            }
     400            return result;
     401        }
     402
     403        @Override
     404        public List<PolygonLevel> call() throws Exception {
     405            for (int i = from; i<to; i++) {
     406                if (processOuterWay(0, input, output, input.get(i)) == null) {
     407                    return null;
     408                }
     409            }
     410            return output;
     411        }
     412    }
    325413}
  • trunk/src/org/openstreetmap/josm/data/osm/visitor/paint/StyledMapRenderer.java

    r7386 r7423  
    3333import java.util.concurrent.ExecutionException;
    3434import java.util.concurrent.ExecutorService;
    35 import java.util.concurrent.Executors;
    3635import java.util.concurrent.Future;
    3736
     
    7372import org.openstreetmap.josm.tools.CompositeList;
    7473import org.openstreetmap.josm.tools.ImageProvider;
     74import org.openstreetmap.josm.tools.Pair;
    7575import org.openstreetmap.josm.tools.Utils;
    7676
    7777/**
    78  * <p>A map renderer which renders a map according to style rules in a set of style sheets.</p>
    79  *
     78 * A map renderer which renders a map according to style rules in a set of style sheets.
     79 * @since 486
    8080 */
    8181public class StyledMapRenderer extends AbstractMapRenderer {
    8282
    83     final public static int noThreads;
    84     final public static ExecutorService styleCreatorPool;
    85 
    86     static {
    87         noThreads = Main.pref.getInteger(
    88                 "mappaint.StyledMapRenderer.style_creation.numberOfThreads",
    89                 Runtime.getRuntime().availableProcessors());
    90         styleCreatorPool = noThreads <= 1 ? null : Executors.newFixedThreadPool(noThreads);
    91     }
     83    private static final Pair<Integer, ExecutorService> THREAD_POOL =
     84            Utils.newThreadPool("mappaint.StyledMapRenderer.style_creation.numberOfThreads");
    9285
    9386    /**
     
    12451238                Main.pref.getBoolean("mappaint.use-antialiasing", true) ?
    12461239                        RenderingHints.VALUE_ANTIALIAS_ON : RenderingHints.VALUE_ANTIALIAS_OFF);
    1247            
     1240
    12481241        highlightLineWidth = Main.pref.getInteger("mappaint.highlight.width", 4);
    12491242        highlightPointRadius = Main.pref.getInteger("mappaint.highlight.radius", 7);
     
    14411434        void process(List<? extends OsmPrimitive> prims) {
    14421435            final List<ComputeStyleListWorker> tasks = new ArrayList<>();
    1443             final int bucketsize = Math.max(100, prims.size()/noThreads/3);
     1436            final int bucketsize = Math.max(100, prims.size()/THREAD_POOL.a/3);
    14441437            final int noBuckets = (prims.size() + bucketsize - 1) / bucketsize;
    1445             final boolean singleThread = noThreads == 1 || noBuckets == 1;
     1438            final boolean singleThread = THREAD_POOL.a == 1 || noBuckets == 1;
    14461439            for (int i=0; i<noBuckets; i++) {
    14471440                int from = i*bucketsize;
     
    14581451                    throw new RuntimeException(ex);
    14591452                }
    1460             } else if (tasks.size() > 1) {
     1453            } else if (!tasks.isEmpty()) {
    14611454                try {
    1462                     for (Future<List<StyleRecord>> future : styleCreatorPool.invokeAll(tasks)) {
    1463                             allStyleElems.addAll(future.get());
     1455                    for (Future<List<StyleRecord>> future : THREAD_POOL.b.invokeAll(tasks)) {
     1456                        allStyleElems.addAll(future.get());
    14641457                    }
    14651458                } catch (InterruptedException | ExecutionException ex) {
  • trunk/src/org/openstreetmap/josm/tools/Utils.java

    r7356 r7423  
    4242import java.util.Iterator;
    4343import java.util.List;
     44import java.util.concurrent.ExecutorService;
     45import java.util.concurrent.Executors;
    4446import java.util.regex.Matcher;
    4547import java.util.regex.Pattern;
     
    10641066        return true;
    10651067    }
     1068
     1069    /**
     1070     * Returns a pair containing the number of threads (n), and a thread pool (if n > 1) to perform
     1071     * multi-thread computation in the context of the given preference key.
     1072     * @param pref The preference key
     1073     * @return a pair containing the number of threads (n), and a thread pool (if n > 1, null otherwise)
     1074     * @since 7423
     1075     */
     1076    public static Pair<Integer, ExecutorService> newThreadPool(String pref) {
     1077        int noThreads = Main.pref.getInteger(pref, Runtime.getRuntime().availableProcessors());
     1078        ExecutorService pool = noThreads <= 1 ? null : Executors.newFixedThreadPool(noThreads);
     1079        return new Pair<>(noThreads, pool);
     1080    }
    10661081}
Note: See TracChangeset for help on using the changeset viewer.