Changeset 11227 in josm for trunk/src/org


Ignore:
Timestamp:
2016-11-09T23:11:04+01:00 (3 years ago)
Author:
bastiK
Message:

applied #13307 - various improvements to MultipolygonTest (patch by Gerd Petermann)

Location:
trunk/src/org/openstreetmap/josm/data
Files:
2 edited

Legend:

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

    r9371 r11227  
    115115    }
    116116
     117    /**
     118     * Checks whether this segment and another way segment share the same points
     119     * @param s2 The other segment
     120     * @return true if other way segment is the same or reverse
     121     */
     122    public boolean isSimilar(WaySegment s2) {
     123        if (getFirstNode().equals(s2.getFirstNode()) && getSecondNode().equals(s2.getSecondNode()))
     124            return true;
     125        if (getFirstNode().equals(s2.getSecondNode()) && getSecondNode().equals(s2.getFirstNode()))
     126            return true;
     127        return false;
     128    }
     129
    117130    @Override
    118131    public String toString() {
  • trunk/src/org/openstreetmap/josm/data/validation/tests/MultipolygonTest.java

    r11222 r11227  
    66import static org.openstreetmap.josm.tools.I18n.trn;
    77
    8 import java.awt.geom.GeneralPath;
     8import java.awt.geom.Area;
     9import java.awt.geom.Point2D;
    910import java.util.ArrayList;
    1011import java.util.Arrays;
    1112import java.util.Collection;
    12 import java.util.Collections;
    1313import java.util.HashMap;
    1414import java.util.HashSet;
     
    1818import java.util.Set;
    1919
    20 import org.openstreetmap.josm.actions.CreateMultipolygonAction;
     20import org.openstreetmap.josm.Main;
    2121import org.openstreetmap.josm.command.ChangeCommand;
    2222import org.openstreetmap.josm.command.Command;
     23import org.openstreetmap.josm.data.coor.EastNorth;
    2324import org.openstreetmap.josm.data.osm.Node;
    2425import org.openstreetmap.josm.data.osm.OsmPrimitive;
     
    2627import org.openstreetmap.josm.data.osm.RelationMember;
    2728import org.openstreetmap.josm.data.osm.Way;
     29import org.openstreetmap.josm.data.osm.WaySegment;
    2830import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon;
    2931import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.PolyData;
    30 import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.PolyData.Intersection;
    3132import org.openstreetmap.josm.data.validation.OsmValidator;
    3233import org.openstreetmap.josm.data.validation.Severity;
     
    3839import org.openstreetmap.josm.gui.mappaint.styleelement.AreaElement;
    3940import org.openstreetmap.josm.gui.progress.ProgressMonitor;
    40 import org.openstreetmap.josm.tools.Pair;
     41import org.openstreetmap.josm.tools.Geometry;
     42import org.openstreetmap.josm.tools.Geometry.PolygonIntersection;
    4143
    4244/**
     
    7476    /** Multipolygon member repeated (same primitive, different role) */
    7577    public static final int REPEATED_MEMBER_DIFF_ROLE = 1615;
    76 
    77     private static volatile ElemStyles styles;
     78    /** Multipolygon ring is equal to another ring */
     79    public static final int EQUAL_RINGS = 1616;
     80    /** Multipolygon rings share nodes */
     81    public static final int RINGS_SHARE_NODES = 1617;
    7882
    7983    private final Set<String> keysCheckedByAnotherTest = new HashSet<>();
     
    8993    @Override
    9094    public void initialize() {
    91         styles = MapPaintStyles.getStyles();
    9295    }
    9396
     
    110113    }
    111114
    112     private static GeneralPath createPath(List<Node> nodes) {
    113         GeneralPath result = new GeneralPath();
    114         result.moveTo((float) nodes.get(0).getCoor().lat(), (float) nodes.get(0).getCoor().lon());
    115         for (int i = 1; i < nodes.size(); i++) {
    116             Node n = nodes.get(i);
    117             result.lineTo((float) n.getCoor().lat(), (float) n.getCoor().lon());
    118         }
    119         return result;
    120     }
    121 
    122     private static List<GeneralPath> createPolygons(List<Multipolygon.PolyData> joinedWays) {
    123         List<GeneralPath> result = new ArrayList<>();
    124         for (Multipolygon.PolyData way : joinedWays) {
    125             result.add(createPath(way.getNodes()));
    126         }
    127         return result;
    128     }
    129 
    130     private static Intersection getPolygonIntersection(GeneralPath outer, List<Node> inner) {
    131         boolean inside = false;
    132         boolean outside = false;
    133 
    134         for (Node n : inner) {
    135             boolean contains = outer.contains(n.getCoor().lat(), n.getCoor().lon());
    136             inside = inside | contains;
    137             outside = outside | !contains;
    138             if (inside & outside) {
    139                 return Intersection.CROSSING;
    140             }
    141         }
    142 
    143         return inside ? Intersection.INSIDE : Intersection.OUTSIDE;
    144     }
    145 
    146115    @Override
    147116    public void visit(Way w) {
     
    164133    @Override
    165134    public void visit(Relation r) {
    166         if (r.isMultipolygon()) {
     135        if (r.isMultipolygon() && r.getMembersCount() > 0) {
    167136            checkMembersAndRoles(r);
    168137            checkOuterWay(r);
    169             checkRepeatedWayMembers(r);
    170 
    171             // Rest of checks is only for complete multipolygons
    172             if (!r.hasIncompleteMembers()) {
    173                 Multipolygon polygon = new Multipolygon(r);
    174 
    175                 // Create new multipolygon using the logics from CreateMultipolygonAction and see if roles match.
    176                 checkMemberRoleCorrectness(r);
    177                 checkStyleConsistency(r, polygon);
    178                 checkGeometry(r, polygon);
     138            boolean hasRepeatedMembers = checkRepeatedWayMembers(r);
     139            if (!hasRepeatedMembers) {
     140                // Rest of checks is only for complete multipolygon
     141                if (!r.hasIncompleteMembers()) {
     142                    Multipolygon polygon = new Multipolygon(r);
     143                    checkStyleConsistency(r, polygon);
     144                    checkGeometryAndRoles(r, polygon);
     145                }
    179146            }
    180147        }
     
    188155     */
    189156    private void checkOuterWay(Relation r) {
    190         boolean hasOuterWay = false;
    191157        for (RelationMember m : r.getMembers()) {
    192             if ("outer".equals(m.getRole())) {
    193                 hasOuterWay = true;
    194                 break;
    195             }
    196         }
    197         if (!hasOuterWay) {
    198             errors.add(TestError.builder(this, Severity.WARNING, MISSING_OUTER_WAY)
    199                     .message(tr("No outer way for multipolygon"))
    200                     .primitives(r)
    201                     .build());
    202         }
    203     }
    204 
    205     /**
    206      * Create new multipolygon using the logics from CreateMultipolygonAction and see if roles match:<ul>
    207      * <li>{@link #WRONG_MEMBER_ROLE}: Role for ''{0}'' should be ''{1}''</li>
    208      * </ul>
    209      * @param r relation
    210      */
    211     private void checkMemberRoleCorrectness(Relation r) {
    212         final Pair<Relation, Relation> newMP = CreateMultipolygonAction.createMultipolygonRelation(r.getMemberPrimitives(Way.class), false);
    213         if (newMP != null) {
    214             for (RelationMember member : r.getMembers()) {
    215                 final Collection<RelationMember> memberInNewMP = newMP.b.getMembersFor(Collections.singleton(member.getMember()));
    216                 if (memberInNewMP != null && !memberInNewMP.isEmpty()) {
    217                     final String roleInNewMP = memberInNewMP.iterator().next().getRole();
    218                     if (!member.getRole().equals(roleInNewMP)) {
    219                         errors.add(TestError.builder(this, Severity.WARNING, WRONG_MEMBER_ROLE)
    220                                 .message(RelationChecker.ROLE_VERIF_PROBLEM_MSG,
    221                                         marktr("Role for ''{0}'' should be ''{1}''"),
    222                                         member.getMember().getDisplayName(DefaultNameFormatter.getInstance()), roleInNewMP)
    223                                 .primitives(addRelationIfNeeded(r, member.getMember()))
    224                                 .highlight(member.getMember())
    225                                 .build());
    226                     }
    227                 }
    228             }
    229         }
     158            if (m.isWay() && "outer".equals(m.getRole())) {
     159                return;
     160            }
     161        }
     162        errors.add(TestError.builder(this, Severity.WARNING, MISSING_OUTER_WAY)
     163                .message(tr("No outer way for multipolygon"))
     164                .primitives(r)
     165                .build());
    230166    }
    231167
     
    241177     */
    242178    private void checkStyleConsistency(Relation r, Multipolygon polygon) {
     179        ElemStyles styles = MapPaintStyles.getStyles();
    243180        if (styles != null && !"boundary".equals(r.get("type"))) {
    244181            AreaElement area = ElemStyles.getAreaElemStyle(r, false);
     
    275212                        errors.add(TestError.builder(this, Severity.OTHER, INNER_STYLE_MISMATCH)
    276213                                .message(tr("With the currently used mappaint style the style for inner way equals the multipolygon style"))
    277                                 .primitives(addRelationIfNeeded(r, wInner))
     214                                .primitives(Arrays.asList(r, wInner))
    278215                                .highlight(wInner)
    279216                                .build());
     
    288225                            errors.add(TestError.builder(this, Severity.OTHER, OUTER_STYLE_MISMATCH)
    289226                                    .message(message)
    290                                     .primitives(addRelationIfNeeded(r, wOuter))
     227                                    .primitives(Arrays.asList(r, wOuter))
    291228                                    .highlight(wOuter)
    292229                                    .build());
     
    294231                            errors.add(TestError.builder(this, Severity.WARNING, OUTER_STYLE)
    295232                                    .message(tr("Area style on outer way"))
    296                                     .primitives(addRelationIfNeeded(r, wOuter))
     233                                    .primitives(Arrays.asList(r, wOuter))
    297234                                    .highlight(wOuter)
    298235                                    .build());
     
    313250     * @param polygon multipolygon
    314251     */
    315     private void checkGeometry(Relation r, Multipolygon polygon) {
     252    private void checkGeometryAndRoles(Relation r, Multipolygon polygon) {
     253        int oldErrorsSize = errors.size();
     254
    316255        List<Node> openNodes = polygon.getOpenEnds();
    317256        if (!openNodes.isEmpty()) {
    318257            errors.add(TestError.builder(this, Severity.WARNING, NON_CLOSED_WAY)
    319258                    .message(tr("Multipolygon is not closed"))
    320                     .primitives(addRelationIfNeeded(r, openNodes))
     259                    .primitives(combineRelAndPrimitives(r, openNodes))
    321260                    .highlight(openNodes)
    322261                    .build());
    323262        }
    324 
    325         // For painting is used Polygon class which works with ints only. For validation we need more precision
     263        Map<Long, RelationMember> wayMap = new HashMap<>();
     264        for (int i = 0; i < r.getMembersCount(); i++) {
     265            RelationMember mem = r.getMember(i);
     266            if (!mem.isWay())
     267                continue;
     268            wayMap.put(mem.getWay().getUniqueId(), mem); // duplicate members were checked before
     269        }
     270        if (wayMap.isEmpty())
     271            return;
     272
     273        Set<Node> sharedNodes = findIntersectionNodes(r);
    326274        List<PolyData> innerPolygons = polygon.getInnerPolygons();
    327275        List<PolyData> outerPolygons = polygon.getOuterPolygons();
    328         List<GeneralPath> innerPolygonsPaths = innerPolygons.isEmpty() ? Collections.<GeneralPath>emptyList() : createPolygons(innerPolygons);
    329         List<GeneralPath> outerPolygonsPaths = createPolygons(outerPolygons);
    330         for (int i = 0; i < outerPolygons.size(); i++) {
    331             PolyData pdOuter = outerPolygons.get(i);
    332             // Check for intersection between outer members
    333             for (int j = i+1; j < outerPolygons.size(); j++) {
    334                 checkCrossingWays(r, outerPolygons, outerPolygonsPaths, pdOuter, j);
    335             }
    336         }
    337         for (int i = 0; i < innerPolygons.size(); i++) {
    338             PolyData pdInner = innerPolygons.get(i);
    339             // Check for intersection between inner members
    340             for (int j = i+1; j < innerPolygons.size(); j++) {
    341                 checkCrossingWays(r, innerPolygons, innerPolygonsPaths, pdInner, j);
    342             }
    343             // Check for intersection between inner and outer members
    344             boolean outside = true;
    345             for (int o = 0; o < outerPolygons.size(); o++) {
    346                 outside &= checkCrossingWays(r, outerPolygons, outerPolygonsPaths, pdInner, o) == Intersection.OUTSIDE;
    347             }
    348             if (outside) {
    349                 errors.add(TestError.builder(this, Severity.WARNING, INNER_WAY_OUTSIDE)
    350                         .message(tr("Multipolygon inner way is outside"))
    351                         .primitives(r)
    352                         .highlightNodePairs(Collections.singletonList(pdInner.getNodes()))
     276        List<PolyData> allPolygons = new ArrayList<>();
     277        allPolygons.addAll(outerPolygons);
     278        allPolygons.addAll(innerPolygons);
     279        Map<PolyData, List<PolyData>> crossingPolyMap = findIntersectingWays(r, innerPolygons, outerPolygons);
     280
     281        if (!sharedNodes.isEmpty()) {
     282            for (int i = 0; i < allPolygons.size(); i++) {
     283                PolyData pd1 = allPolygons.get(i);
     284                for (int j = i + 1; j < allPolygons.size(); j++) {
     285                    PolyData pd2 = allPolygons.get(j);
     286                    if (!checkProblemMap(crossingPolyMap, pd1, pd2)) {
     287                        checkPolygonsForSharedNodes(r, pd1, pd2, sharedNodes, wayMap);
     288                    }
     289                }
     290            }
     291        }
     292        boolean checkRoles = true;
     293        for (int i = oldErrorsSize; i < errors.size(); i++) {
     294            if (errors.get(i).getSeverity() != Severity.OTHER) {
     295                checkRoles = false;
     296                break;
     297            }
     298        }
     299        if (checkRoles) {
     300            // we found no intersection or crossing between the polygons and they are closed
     301            // now we can calculate the nesting level to verify the roles with some simple node checks
     302            checkRoles(r, allPolygons, wayMap, sharedNodes);
     303        }
     304    }
     305
     306    /**
     307     * Detect intersections of multipolygon ways at nodes. If any way node is used by more than two ways
     308     * or two times in one way and at least once in another way we found an intersection.
     309     * @param r the relation
     310     * @return List of nodes were ways intersect
     311     */
     312    private Set<Node> findIntersectionNodes(Relation r) {
     313        Set<Node> intersectionNodes = new HashSet<>();
     314        Map<Node, List<Way>> nodeMap = new HashMap<>();
     315        for (RelationMember rm : r.getMembers()) {
     316            if (!rm.isWay())
     317                continue;
     318            int numNodes = rm.getWay().getNodesCount();
     319            for (int i = 0; i < numNodes; i++) {
     320                Node n = rm.getWay().getNode(i);
     321                if (n.getReferrers().size() <= 1) {
     322                    continue; // cannot be a problem node
     323                }
     324                List<Way> ways = nodeMap.get(n);
     325                if (ways == null) {
     326                    ways = new ArrayList<>();
     327                    nodeMap.put(n, ways);
     328                }
     329                ways.add(rm.getWay());
     330                if (ways.size() > 2 || (ways.size() == 2 && i != 0 && i + 1 != numNodes)) {
     331                    intersectionNodes.add(n);
     332                }
     333            }
     334        }
     335        return intersectionNodes;
     336    }
     337
     338    private enum ExtPolygonIntersection {
     339        EQUAL,
     340        FIRST_INSIDE_SECOND,
     341        SECOND_INSIDE_FIRST,
     342        OUTSIDE,
     343        CROSSING
     344    }
     345
     346    private void checkPolygonsForSharedNodes(Relation r, PolyData pd1, PolyData pd2, Set<Node> allSharedNodes,
     347            Map<Long, RelationMember> wayMap) {
     348        Set<Node> sharedByPolygons = new HashSet<>(allSharedNodes);
     349        sharedByPolygons.retainAll(pd1.getNodes());
     350        sharedByPolygons.retainAll(pd2.getNodes());
     351        if (sharedByPolygons.isEmpty())
     352            return;
     353
     354        // the two polygons share one or more nodes
     355        // 1st might be equal to 2nd (same nodes, same or different direction) --> error shared way segments
     356        // they overlap --> error
     357        // 1st and 2nd share segments
     358        // 1st fully inside 2nd --> okay
     359        // 2nd fully inside 1st --> okay
     360        int errorCode = RINGS_SHARE_NODES;
     361        ExtPolygonIntersection res = checkOverlapAtSharedNodes(sharedByPolygons, pd1, pd2);
     362        if (res == ExtPolygonIntersection.CROSSING) {
     363            errorCode = CROSSING_WAYS;
     364        } else if (res == ExtPolygonIntersection.EQUAL) {
     365            errorCode = EQUAL_RINGS;
     366        }
     367        if (errorCode != 0) {
     368            Set<OsmPrimitive> prims = new HashSet<>();
     369            prims.add(r);
     370            for (Node n : sharedByPolygons) {
     371                for (OsmPrimitive p : n.getReferrers()) {
     372                    if (p instanceof Way && (pd1.getWayIds().contains(p.getUniqueId()) || pd2.getWayIds().contains(p.getUniqueId()))) {
     373                        prims.add(p);
     374                    }
     375                }
     376            }
     377            if (errorCode == RINGS_SHARE_NODES) {
     378                errors.add(TestError.builder(this, Severity.OTHER, errorCode)
     379                        .message(tr("Multipolygon rings share node(s)"))
     380                        .primitives(prims)
     381                        .highlight(sharedByPolygons)
    353382                        .build());
    354             }
    355         }
    356     }
    357 
    358     private Intersection checkCrossingWays(Relation r, List<PolyData> polygons, List<GeneralPath> polygonsPaths, PolyData pd, int idx) {
    359         Intersection intersection = getPolygonIntersection(polygonsPaths.get(idx), pd.getNodes());
    360         if (intersection == Intersection.CROSSING) {
    361             PolyData pdOther = polygons.get(idx);
    362             if (pdOther != null) {
    363                 errors.add(TestError.builder(this, Severity.WARNING, CROSSING_WAYS)
    364                         .message(tr("Intersection between multipolygon ways"))
    365                         .primitives(r)
    366                         .highlightNodePairs(Arrays.asList(pd.getNodes(), pdOther.getNodes()))
     383            } else {
     384                errors.add(TestError.builder(this, Severity.WARNING, errorCode)
     385                        .message(errorCode == CROSSING_WAYS ? tr("Intersection between multipolygon ways") : tr("Multipolygon rings are equal"))
     386                        .primitives(prims)
     387                        .highlight(sharedByPolygons)
    367388                        .build());
    368389            }
    369390        }
    370         return intersection;
     391    }
     392
     393    private ExtPolygonIntersection checkOverlapAtSharedNodes(Set<Node> shared, PolyData pd1, PolyData pd2) {
     394        // Idea: if two polygons share one or more nodes they can either just touch or share segments or intersect.
     395        // The insideness test is complex, so we try to reduce the number of these tests.
     396        // There is no need to check all nodes, we only have to check the node following a shared node.
     397
     398        final int FOUND_INSIDE = 1;
     399        final int FOUND_OUTSIDE = 2;
     400        int[] flags = new int[2];
     401        for (int loop = 0; loop < flags.length; loop++) {
     402            List<Node> nodes2Test = loop == 0 ? pd1.getNodes() : pd2.getNodes();
     403            int num = nodes2Test.size() - 1; // ignore closing duplicate node
     404
     405
     406            int lenShared = 0;
     407            for (int i = 0; i < num; i++) {
     408                Node n = nodes2Test.get(i);
     409                if (shared.contains(n)) {
     410                    ++lenShared;
     411                } else {
     412                    if (i == 0 || lenShared > 0) {
     413                        // do we have to treat lenShared > 1 special ?
     414                        lenShared = 0;
     415                        boolean inside = checkIfNodeIsInsidePolygon(n, loop == 0 ? pd2 : pd1);
     416                        flags[loop] |= inside ? FOUND_INSIDE : FOUND_OUTSIDE;
     417                        if (flags[loop] == (FOUND_INSIDE | FOUND_OUTSIDE)) {
     418                            return ExtPolygonIntersection.CROSSING;
     419                        }
     420                    }
     421                }
     422            }
     423        }
     424
     425        if ((flags[0] & FOUND_INSIDE) != 0)
     426            return ExtPolygonIntersection.FIRST_INSIDE_SECOND;
     427        if ((flags[1] & FOUND_INSIDE) != 0)
     428            return ExtPolygonIntersection.SECOND_INSIDE_FIRST;
     429        if ((flags[0] & FOUND_OUTSIDE) != (flags[1] & FOUND_OUTSIDE)) {
     430            return (flags[0] & FOUND_OUTSIDE) != 0 ?
     431                ExtPolygonIntersection.SECOND_INSIDE_FIRST : ExtPolygonIntersection.FIRST_INSIDE_SECOND;
     432        }
     433        if ((flags[0] & FOUND_OUTSIDE) != 0 && (flags[1] & FOUND_OUTSIDE) != 0) {
     434            // the two polygons may only share one or more segments but they may also intersect
     435            Area a1 = new Area(pd1.get());
     436            Area a2 = new Area(pd2.get());
     437            PolygonIntersection areaRes = Geometry.polygonIntersection(a1, a2, 1e-6);
     438            if (areaRes == PolygonIntersection.OUTSIDE)
     439                return ExtPolygonIntersection.OUTSIDE;
     440            return ExtPolygonIntersection.CROSSING;
     441        }
     442        return ExtPolygonIntersection.EQUAL;
     443    }
     444
     445    /**
     446     * Helper class for calculation of nesting levels
     447     */
     448    private static class PolygonLevel {
     449        public final int level; // nesting level, even for outer, odd for inner polygons.
     450        public final PolyData outerWay;
     451
     452        PolygonLevel(PolyData pd, int level) {
     453            this.outerWay = pd;
     454            this.level = level;
     455        }
     456    }
     457
     458    /**
     459     * Calculate the nesting levels of the polygon rings and check if calculated role matches
     460     * @param r relation (for error reporting)
     461     * @param allPolygons list of polygon rings
     462     * @param wayMap maps way ids to relation members
     463     * @param sharedNodes all nodes shared by multiple ways of this multipolygon
     464     */
     465    private void checkRoles(Relation r, List<PolyData> allPolygons, Map<Long, RelationMember> wayMap, Set<Node> sharedNodes) {
     466        PolygonLevelFinder levelFinder = new PolygonLevelFinder(sharedNodes);
     467        List<PolygonLevel> list = levelFinder.findOuterWays(allPolygons);
     468        if (list == null || list.isEmpty()) {
     469            return;
     470        }
     471
     472        for (PolygonLevel pol : list) {
     473            String calculatedRole = (pol.level % 2 == 0) ? "outer" : "inner";
     474            for (long wayId : pol.outerWay.getWayIds()) {
     475                RelationMember member = wayMap.get(wayId);
     476                if (!member.getRole().equals(calculatedRole)) {
     477                    errors.add(TestError.builder(this, Severity.WARNING, WRONG_MEMBER_ROLE)
     478                            .message(RelationChecker.ROLE_VERIF_PROBLEM_MSG,
     479                                    marktr("Role for ''{0}'' should be ''{1}''"),
     480                                    member.getMember().getDisplayName(DefaultNameFormatter.getInstance()),
     481                                    calculatedRole)
     482                            .primitives(Arrays.asList(r, member.getMember()))
     483                            .highlight(member.getMember())
     484                            .build());
     485                    if (pol.level == 0 && "inner".equals(member.getRole())) {
     486                        // maybe only add this error if we found an outer ring with correct role(s) ?
     487                        errors.add(TestError.builder(this, Severity.WARNING, INNER_WAY_OUTSIDE)
     488                                .message(tr("Multipolygon inner way is outside"))
     489                                .primitives(Arrays.asList(r, member.getMember()))
     490                                .highlight(member.getMember())
     491                                .build());
     492                    }
     493                }
     494            }
     495        }
     496    }
     497
     498    /**
     499     * Check if a node is inside the polygon according to the insideness rules of Shape.
     500     * @param n the node
     501     * @param p the polygon
     502     * @return true if the node is inside the polygon
     503     */
     504    private static boolean checkIfNodeIsInsidePolygon(Node n, PolyData p) {
     505        EastNorth en = n.getEastNorth();
     506        return (en != null && p.get().contains(en.getX(), en.getY()));
     507    }
     508
     509    /**
     510     * Determine multipolygon ways which are intersecting (crossing without a common node) or sharing one or more way segments.
     511     * See also {@link CrossingWays}
     512     * @param r the relation (for error reporting)
     513     * @param innerPolygons list of inner polygons
     514     * @param outerPolygons list of outer polygons
     515     * @return map with crossing polygons
     516     */
     517    private Map<PolyData, List<PolyData>> findIntersectingWays(Relation r, List<PolyData> innerPolygons,
     518            List<PolyData> outerPolygons) {
     519        HashMap<PolyData, List<PolyData>> crossingPolygonsMap = new HashMap<>();
     520        HashMap<PolyData, List<PolyData>> sharedWaySegmentsPolygonsMap = new HashMap<>();
     521
     522        for (int loop = 0; loop < 2; loop++) {
     523            /** All way segments, grouped by cells */
     524            final Map<Point2D, List<WaySegment>> cellSegments = new HashMap<>(1000);
     525            /** The already detected ways in error */
     526            final Map<List<Way>, List<WaySegment>> problemWays = new HashMap<>(50);
     527
     528            Map<PolyData, List<PolyData>> problemPolygonMap = (loop == 0) ? crossingPolygonsMap
     529                    : sharedWaySegmentsPolygonsMap;
     530
     531            for (Way w : r.getMemberPrimitives(Way.class)) {
     532                findIntersectingWay(w, r, cellSegments, problemWays, loop == 1);
     533            }
     534
     535            if (!problemWays.isEmpty()) {
     536                List<PolyData> allPolygons = new ArrayList<>(innerPolygons.size() + outerPolygons.size());
     537                allPolygons.addAll(innerPolygons);
     538                allPolygons.addAll(outerPolygons);
     539
     540                for (Entry<List<Way>, List<WaySegment>> entry : problemWays.entrySet()) {
     541                    List<Way> ways = entry.getKey();
     542                    if (ways.size() != 2)
     543                        continue;
     544                    PolyData[] crossingPolys = new PolyData[2];
     545                    boolean allInner = true;
     546                    for (int i = 0; i < 2; i++) {
     547                        Way w = ways.get(i);
     548                        for (int j = 0; j < allPolygons.size(); j++) {
     549                            PolyData pd = allPolygons.get(j);
     550                            if (pd.getWayIds().contains(w.getUniqueId())) {
     551                                crossingPolys[i] = pd;
     552                                if (j >= innerPolygons.size())
     553                                    allInner = false;
     554                                break;
     555                            }
     556                        }
     557                    }
     558                    boolean samePoly = false;
     559                    if (crossingPolys[0] != null && crossingPolys[1] != null) {
     560                        List<PolyData> crossingPolygons = problemPolygonMap.get(crossingPolys[0]);
     561                        if (crossingPolygons == null) {
     562                            crossingPolygons = new ArrayList<>();
     563                            problemPolygonMap.put(crossingPolys[0], crossingPolygons);
     564                        }
     565                        crossingPolygons.add(crossingPolys[1]);
     566                        if (crossingPolys[0] == crossingPolys[1]) {
     567                            samePoly = true;
     568                        }
     569                    }
     570                    if (loop == 0 || samePoly || (loop == 1 && !allInner)) {
     571                        String msg = loop == 0 ? tr("Intersection between multipolygon ways")
     572                                : samePoly ? tr("Multipolygon ring contains segments twice")
     573                                        : tr("Multipolygon outer way shares segment(s) with other ring");
     574                        errors.add(TestError.builder(this, Severity.WARNING, CROSSING_WAYS)
     575                                .message(msg)
     576                                .primitives(Arrays.asList(r, ways.get(0), ways.get(1)))
     577                                .highlightWaySegments(entry.getValue())
     578                                .build());
     579                    }
     580                }
     581            }
     582        }
     583        return crossingPolygonsMap;
     584    }
     585
     586    /**
     587     * Find ways which are crossing without sharing a node.
     588     * @param w way that is member of the relation
     589     * @param r the relation (used for error messages)
     590     * @param cellSegments map with already collected way segments
     591     * @param crossingWays list to collect crossing ways
     592     * @param findSharedWaySegments true: find shared way segments instead of crossings
     593     */
     594    private void findIntersectingWay(Way w, Relation r, Map<Point2D, List<WaySegment>> cellSegments,
     595            Map<List<Way>, List<WaySegment>> crossingWays, boolean findSharedWaySegments) {
     596        int nodesSize = w.getNodesCount();
     597        for (int i = 0; i < nodesSize - 1; i++) {
     598            final WaySegment es1 = new WaySegment(w, i);
     599            final EastNorth en1 = es1.getFirstNode().getEastNorth();
     600            final EastNorth en2 = es1.getSecondNode().getEastNorth();
     601            if (en1 == null || en2 == null) {
     602                Main.warn("Crossing ways test (MP) skipped " + es1);
     603                continue;
     604            }
     605            for (List<WaySegment> segments : CrossingWays.getSegments(cellSegments, en1, en2)) {
     606                for (WaySegment es2 : segments) {
     607
     608                    List<WaySegment> highlight;
     609                    if (es2.way == w)
     610                        continue; // reported by CrossingWays.SelfIntersection
     611                    if (findSharedWaySegments && !es1.isSimilar(es2))
     612                        continue;
     613                    if (!findSharedWaySegments && !es1.intersects(es2))
     614                        continue;
     615
     616                    List<Way> prims = Arrays.asList(es1.way, es2.way);
     617                    if ((highlight = crossingWays.get(prims)) == null) {
     618                        highlight = new ArrayList<>();
     619                        highlight.add(es1);
     620                        highlight.add(es2);
     621                        crossingWays.put(prims, highlight);
     622                    } else {
     623                        highlight.add(es1);
     624                        highlight.add(es2);
     625                    }
     626                }
     627                segments.add(es1);
     628            }
     629        }
     630    }
     631
     632    /**
     633     * Check if map contains combination of two given polygons.
     634     * @param problemPolyMap the map
     635     * @param pd1 1st polygon
     636     * @param pd2 2nd polygon
     637     * @return true if the combination of polygons is found in the map
     638     */
     639    private boolean checkProblemMap(Map<PolyData, List<PolyData>> problemPolyMap, PolyData pd1, PolyData pd2) {
     640        List<PolyData> crossingWithFirst = problemPolyMap.get(pd1);
     641        if (crossingWithFirst != null) {
     642            if (crossingWithFirst.contains(pd2))
     643                return true;
     644        }
     645        List<PolyData> crossingWith2nd = problemPolyMap.get(pd2);
     646        return (crossingWith2nd != null && crossingWith2nd.contains(pd1));
    371647    }
    372648
     
    384660                    errors.add(TestError.builder(this, Severity.WARNING, WRONG_MEMBER_ROLE)
    385661                            .message(tr("No useful role for multipolygon member"))
    386                             .primitives(addRelationIfNeeded(r, rm.getMember()))
     662                            .primitives(Arrays.asList(r, rm.getMember()))
    387663                            .build());
    388664                }
     
    391667                    errors.add(TestError.builder(this, Severity.WARNING, WRONG_MEMBER_TYPE)
    392668                            .message(tr("Non-Way in multipolygon"))
    393                             .primitives(addRelationIfNeeded(r, rm.getMember()))
     669                            .primitives(Arrays.asList(r, rm.getMember()))
    394670                            .build());
    395671                }
     
    398674    }
    399675
    400     private static Collection<? extends OsmPrimitive> addRelationIfNeeded(Relation r, OsmPrimitive primitive) {
    401         return addRelationIfNeeded(r, Collections.singleton(primitive));
    402     }
    403 
    404     private static Collection<? extends OsmPrimitive> addRelationIfNeeded(Relation r, Collection<? extends OsmPrimitive> primitives) {
     676    private static Collection<? extends OsmPrimitive> combineRelAndPrimitives(Relation r, Collection<? extends OsmPrimitive> primitives) {
    405677        // add multipolygon in order to let user select something and fix the error
    406678        if (!primitives.contains(r)) {
     
    468740    private void addRepeatedMemberError(Relation r, List<OsmPrimitive> repeatedMembers, int errorCode, String msg) {
    469741        if (!repeatedMembers.isEmpty()) {
    470             List<OsmPrimitive> prims = new ArrayList<>(1 + repeatedMembers.size());
    471             prims.add(r);
    472             prims.addAll(repeatedMembers);
    473             errors.add(TestError.builder(this, Severity.WARNING, errorCode)
     742            errors.add(TestError.builder(this, Severity.ERROR, errorCode)
    474743                    .message(msg)
    475                     .primitives(prims)
     744                    .primitives(combineRelAndPrimitives(r, repeatedMembers))
    476745                    .highlight(repeatedMembers)
    477746                    .build());
     
    515784        return false;
    516785    }
     786
     787    /**
     788     * Find nesting levels of polygons. Logic taken from class MultipolygonBuilder, uses different structures.
     789     */
     790    private static class PolygonLevelFinder {
     791        private final Set<Node> sharedNodes;
     792
     793        PolygonLevelFinder(Set<Node> sharedNodes) {
     794            this.sharedNodes = sharedNodes;
     795        }
     796
     797        public List<PolygonLevel> findOuterWays(List<PolyData> allPolygons) {
     798            return findOuterWaysRecursive(0, allPolygons);
     799        }
     800
     801        private List<PolygonLevel> findOuterWaysRecursive(int level, List<PolyData> polygons) {
     802            final List<PolygonLevel> result = new ArrayList<>();
     803
     804            for (PolyData pd : polygons) {
     805                if (processOuterWay(level, polygons, result, pd) == null) {
     806                    return null;
     807                }
     808            }
     809
     810            return result;
     811        }
     812
     813        private Object processOuterWay(int level, List<PolyData> polygons, List<PolygonLevel> result, PolyData pd) {
     814            List<PolyData> inners = findInnerWaysCandidates(pd, polygons);
     815
     816            if (inners != null) {
     817                //add new outer polygon
     818                PolygonLevel pol = new PolygonLevel(pd, level);
     819
     820                //process inner ways
     821                if (!inners.isEmpty()) {
     822                    List<PolygonLevel> innerList = findOuterWaysRecursive(level + 1, inners);
     823                    result.addAll(innerList);
     824                }
     825
     826                result.add(pol);
     827            }
     828            return result;
     829        }
     830
     831        /**
     832         * Check if polygon is an out-most ring, if so, collect the inners
     833         * @param outerCandidate polygon which is checked
     834         * @param polygons all polygons
     835         * @return null if outerCandidate is inside any other polygon, else a list of inner polygons (which might be empty)
     836         */
     837        private List<PolyData> findInnerWaysCandidates(PolyData outerCandidate, List<PolyData> polygons) {
     838            List<PolyData> innerCandidates = new ArrayList<>();
     839
     840            for (PolyData inner : polygons) {
     841                if (inner == outerCandidate) {
     842                    continue;
     843                }
     844                if (!outerCandidate.getBounds().intersects(inner.getBounds())) {
     845                    continue;
     846                }
     847
     848                Node unsharedNode = getNonIntersectingNode(outerCandidate, inner);
     849                if (unsharedNode != null) {
     850                    if (checkIfNodeIsInsidePolygon(unsharedNode, outerCandidate)) {
     851                        innerCandidates.add(inner);
     852                    } else {
     853                        // inner is not inside outerCandidate, check if it contains outerCandidate
     854                        unsharedNode = getNonIntersectingNode(inner, outerCandidate);
     855                        if (unsharedNode != null) {
     856                            if (checkIfNodeIsInsidePolygon(unsharedNode, inner)) {
     857                                return null;
     858                            }
     859                        } else {
     860                            return null; // polygons have only common nodes
     861                        }
     862                    }
     863                } else {
     864                    // all nodes of inner are also nodes of outerCandidate
     865                    unsharedNode = getNonIntersectingNode(inner, outerCandidate);
     866                    if (unsharedNode == null) {
     867                        return null;
     868                    } else {
     869                        innerCandidates.add(inner);
     870                    }
     871                }
     872            }
     873            return innerCandidates;
     874        }
     875
     876        /**
     877         * Find node of pd2 which is not an intersection node with pd1.
     878         * @param pd1 1st polygon
     879         * @param pd2 2nd polygon
     880         * @return node of pd2 which is not an intersection node with pd1 or null if none is found
     881         */
     882        private Node getNonIntersectingNode(PolyData pd1, PolyData pd2) {
     883            for (Node n : pd2.getNodes()) {
     884                if (!sharedNodes.contains(n) || !pd1.getNodes().contains(n))
     885                    return n;
     886            }
     887            return null;
     888        }
     889    }
    517890}
Note: See TracChangeset for help on using the changeset viewer.