Changeset 19336 in josm


Ignore:
Timestamp:
2025-02-25T17:29:20+01:00 (7 hours ago)
Author:
stoecker
Message:

fix #24046 - improve speed of multipolygon validator - patch by taylor.smock

Location:
trunk
Files:
6 edited

Legend:

Unmodified
Added
Removed

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

    r19101 r19336  
    155155     */
    156156    public static Pair<List<JoinedPolygon>, List<JoinedPolygon>> joinWays(Relation multipolygon) {
     157        return joinWays(null, multipolygon);
     158    }
     159
     160    /**
     161     * Joins the given {@code multipolygon} to a pair of outer and inner multipolygon rings.
     162     *
     163     * @param multipolygon the multipolygon to join.
     164     * @return a pair of outer and inner multipolygon rings.
     165     * @throws JoinedPolygonCreationException if the creation fails.
     166     * @since xxx
     167     */
     168    public static Pair<List<JoinedPolygon>, List<JoinedPolygon>> joinWays(
     169            Map<IRelation<?>, Pair<List<JoinedPolygon>, List<JoinedPolygon>>> cache, Relation multipolygon) {
     170        if (cache != null) {
     171            return cache.computeIfAbsent(multipolygon, MultipolygonBuilder::joinWaysActual);
     172        }
     173        return joinWaysActual(multipolygon);
     174    }
     175
     176    /**
     177     * Perform the actual join ways calculation
     178     *
     179     * @param multipolygon the multipolygon to join.
     180     * @return a pair of outer and inner multipolygon rings.
     181     * @throws JoinedPolygonCreationException if the creation fails.
     182     */
     183    private static Pair<List<JoinedPolygon>, List<JoinedPolygon>> joinWaysActual(IRelation<?> multipolygon) {
    157184        CheckParameterUtil.ensureThat(multipolygon.isMultipolygon(), "multipolygon.isMultipolygon");
    158         final Map<String, Set<Way>> members = multipolygon.getMembers().stream()
    159                 .filter(RelationMember::isWay)
    160                 .collect(Collectors.groupingBy(RelationMember::getRole, Collectors.mapping(RelationMember::getWay, Collectors.toSet())));
     185        CheckParameterUtil.ensureThat(multipolygon instanceof Relation,
     186                "This method currently only supports Relation objects due to potential breakage");
     187        final Map<String, Set<Way>> members = ((Relation) multipolygon).getMembers().stream()
     188                .filter(IRelationMember::isWay)
     189                .collect(Collectors.groupingBy(IRelationMember::getRole, Collectors.mapping(RelationMember::getWay, Collectors.toSet())));
    161190        final List<JoinedPolygon> outerRings = joinWays(members.getOrDefault("outer", Collections.emptySet()));
    162191        final List<JoinedPolygon> innerRings = joinWays(members.getOrDefault("inner", Collections.emptySet()));

  • trunk/src/org/openstreetmap/josm/data/validation/tests/MapCSSTagChecker.java

    r18801 r19336  
    2525
    2626import org.openstreetmap.josm.data.osm.IPrimitive;
     27import org.openstreetmap.josm.data.osm.IRelation;
     28import org.openstreetmap.josm.data.osm.MultipolygonBuilder.JoinedPolygon;
    2729import org.openstreetmap.josm.data.osm.OsmPrimitive;
    2830import org.openstreetmap.josm.data.preferences.BooleanProperty;
    … …  
    5052import org.openstreetmap.josm.tools.Logging;
    5153import org.openstreetmap.josm.tools.MultiMap;
     54import org.openstreetmap.josm.tools.Pair;
    5255import org.openstreetmap.josm.tools.Stopwatch;
    5356import org.openstreetmap.josm.tools.Utils;
    … …  
    6164    private final Map<MapCSSRule, MapCSSTagCheckerAndRule> ruleToCheckMap = new HashMap<>();
    6265    private static final Map<IPrimitive, Area> mpAreaCache = new HashMap<>();
     66    private static final Map<IRelation<?>, Pair<List<JoinedPolygon>, List<JoinedPolygon>>> mpJoinedAreaCache = new HashMap<>();
    6367    private static final Set<IPrimitive> toMatchForSurrounding = new HashSet<>();
    6468    static final boolean ALL_TESTS = true;
    … …  
    164168        final Environment env = new Environment(p, new MultiCascade(), Environment.DEFAULT_LAYER, null);
    165169        env.mpAreaCache = mpAreaCache;
     170        env.mpJoinedAreaCache = mpJoinedAreaCache;
    166171        env.toMatchForSurrounding = toMatchForSurrounding;
    167172
    … …  
    222227        final Environment env = new Environment(p, new MultiCascade(), Environment.DEFAULT_LAYER, null);
    223228        env.mpAreaCache = mpAreaCache;
     229        env.mpJoinedAreaCache = mpJoinedAreaCache;
    224230        env.toMatchForSurrounding = toMatchForSurrounding;
    225231        for (Set<MapCSSTagCheckerRule> schecks : checksCol) {
    … …  
    377383        mpAreaCache.clear();
    378384        ruleToCheckMap.clear();
     385        mpJoinedAreaCache.clear();
    379386        toMatchForSurrounding.clear();
    380387        super.endTest();
    … …  
    397404
    398405        mpAreaCache.clear();
     406        mpJoinedAreaCache.clear();
    399407        toMatchForSurrounding.clear();
    400408

  • trunk/src/org/openstreetmap/josm/gui/mappaint/Environment.java

    r18918 r19336  
    99
    1010import org.openstreetmap.josm.data.osm.IPrimitive;
     11import org.openstreetmap.josm.data.osm.IRelation;
     12import org.openstreetmap.josm.data.osm.MultipolygonBuilder;
    1113import org.openstreetmap.josm.data.osm.Relation;
    1214import org.openstreetmap.josm.data.osm.Way;
    … …  
    1618import org.openstreetmap.josm.gui.mappaint.mapcss.Selector.LinkSelector;
    1719import org.openstreetmap.josm.tools.CheckParameterUtil;
     20import org.openstreetmap.josm.tools.Pair;
    1821
    1922/**
    … …  
    9194     */
    9295    public Map<IPrimitive, Area> mpAreaCache;
     96    /**
     97     * Cache for multipolygon areas as calculated by {@link MultipolygonBuilder#joinWays(Relation)}, can be {@code null}
     98     */
     99    public Map<IRelation<?>, Pair<List<MultipolygonBuilder.JoinedPolygon>, List<MultipolygonBuilder.JoinedPolygon>>> mpJoinedAreaCache;
    93100
    94101    /**
    … …  
    163170        this.crossingWaysMap = other.crossingWaysMap;
    164171        this.mpAreaCache = other.mpAreaCache;
     172        this.mpJoinedAreaCache = other.mpJoinedAreaCache;
    165173        this.toMatchForSurrounding = other.toMatchForSurrounding;
    166174        this.selector = selector;

  • trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/Selector.java

    r19050 r19336  
    491491                if (r instanceof Relation && r.isMultipolygon() && r.getBBox().bounds(e.osm.getBBox())
    492492                        && left.matches(new Environment(r).withParent(e.osm))
    493                         && !Geometry.filterInsideMultipolygon(Collections.singletonList(e.osm), (Relation) r).isEmpty()) {
     493                        && !Geometry.filterInsideMultipolygon(Collections.singletonList(e.osm), (Relation) r, e.mpJoinedAreaCache).isEmpty()) {
    494494                    addToChildren(e, r);
    495495                }

  • trunk/src/org/openstreetmap/josm/tools/Geometry.java

    r19272 r19336  
    1818import java.util.LinkedHashSet;
    1919import java.util.List;
     20import java.util.Map;
    2021import java.util.Set;
    2122import java.util.TreeSet;
    … …  
    3334import org.openstreetmap.josm.data.osm.INode;
    3435import org.openstreetmap.josm.data.osm.IPrimitive;
     36import org.openstreetmap.josm.data.osm.IRelation;
    3537import org.openstreetmap.josm.data.osm.IWay;
    3638import org.openstreetmap.josm.data.osm.MultipolygonBuilder;
    … …  
    11921194                    polygonArea = getArea(polygon.getNodes());
    11931195                }
    1194                 Multipolygon mp = new Multipolygon((Relation) p);
     1196                Multipolygon mp = p.getDataSet() != null ? MultipolygonCache.getInstance().get((Relation) p) : new Multipolygon((Relation) p);
    11951197                boolean inside = true;
    11961198                // a (valid) multipolygon is inside the polygon if all outer rings are inside
    … …  
    12211223     */
    12221224    public static List<IPrimitive> filterInsideMultipolygon(Collection<IPrimitive> primitives, Relation multiPolygon) {
     1225        return filterInsideMultipolygon(primitives, multiPolygon, null);
     1226    }
     1227
     1228    /**
     1229     * Find all primitives in the given collection which are inside the given multipolygon. Members of the multipolygon are
     1230     * ignored. Unclosed ways and multipolygon relations with unclosed outer rings are ignored.
     1231     * @param primitives the primitives
     1232     * @param multiPolygon the multipolygon relation
     1233     * @param cache The cache to avoid calculating joined inner/outer ways multiple times (see {@link MultipolygonBuilder#joinWays(Relation)})
     1234     * @return a new list containing the found primitives, empty if multipolygon is invalid or nothing was found.
     1235     * @since xxx
     1236     */
     1237    public static List<IPrimitive> filterInsideMultipolygon(Collection<IPrimitive> primitives, Relation multiPolygon,
     1238                                                            Map<IRelation<?>, Pair<List<JoinedPolygon>, List<JoinedPolygon>>> cache) {
    12231239        List<IPrimitive> res = new ArrayList<>();
    12241240        if (primitives.isEmpty())
    … …  
    12271243        final Pair<List<JoinedPolygon>, List<JoinedPolygon>> outerInner;
    12281244        try {
    1229             outerInner = MultipolygonBuilder.joinWays(multiPolygon);
     1245            outerInner = MultipolygonBuilder.joinWays(cache, multiPolygon);
    12301246        } catch (MultipolygonBuilder.JoinedPolygonCreationException ex) {
    12311247            Logging.trace(ex);

  • trunk/test/unit/org/openstreetmap/josm/tools/GeometryTest.java

    r19272 r19336  
    368368        mp2.put("type", "multipolygon");
    369369        assertFalse(Geometry.isPolygonInsideMultiPolygon(w1.getNodes(), mp2, null));
    370         assertFalse(Geometry.filterInsideMultipolygon(Collections.singletonList(w1), mp2).contains(w1));
     370        assertFalse(Geometry.filterInsideMultipolygon(Collections.singletonList(w1), mp2, null).contains(w1));
    371371
    372372        node4.setCoor(new LatLon(1.006, 0.99));
    373373        // now w1 is inside
    374374        assertTrue(Geometry.isPolygonInsideMultiPolygon(w1.getNodes(), mp2, null));
    375         assertTrue(Geometry.filterInsideMultipolygon(Collections.singletonList(w1), mp2).contains(w1));
    376         assertTrue(Geometry.filterInsideMultipolygon(Collections.singletonList(mp1), mp2).contains(mp1));
    377         assertTrue(Geometry.filterInsideMultipolygon(Arrays.asList(w1, mp1), mp2).contains(w1));
    378         assertTrue(Geometry.filterInsideMultipolygon(Arrays.asList(w1, mp1), mp2).contains(mp1));
     375        assertTrue(Geometry.filterInsideMultipolygon(Collections.singletonList(w1), mp2, null).contains(w1));
     376        assertTrue(Geometry.filterInsideMultipolygon(Collections.singletonList(mp1), mp2, null).contains(mp1));
     377        assertTrue(Geometry.filterInsideMultipolygon(Arrays.asList(w1, mp1), mp2, null).contains(w1));
     378        assertTrue(Geometry.filterInsideMultipolygon(Arrays.asList(w1, mp1), mp2, null).contains(mp1));
    379379    }
    380380
Note: See TracChangeset for help on using the changeset viewer.