001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data.validation.tests;
003
004import static org.openstreetmap.josm.tools.I18n.marktr;
005import static org.openstreetmap.josm.tools.I18n.tr;
006import static org.openstreetmap.josm.tools.I18n.trn;
007
008import java.awt.geom.GeneralPath;
009import java.util.ArrayList;
010import java.util.Arrays;
011import java.util.Collection;
012import java.util.Collections;
013import java.util.HashMap;
014import java.util.HashSet;
015import java.util.List;
016import java.util.Map;
017import java.util.Map.Entry;
018import java.util.Set;
019
020import org.openstreetmap.josm.actions.CreateMultipolygonAction;
021import org.openstreetmap.josm.command.ChangeCommand;
022import org.openstreetmap.josm.command.Command;
023import org.openstreetmap.josm.data.osm.Node;
024import org.openstreetmap.josm.data.osm.OsmPrimitive;
025import org.openstreetmap.josm.data.osm.Relation;
026import org.openstreetmap.josm.data.osm.RelationMember;
027import org.openstreetmap.josm.data.osm.Way;
028import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon;
029import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.PolyData;
030import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.PolyData.Intersection;
031import org.openstreetmap.josm.data.validation.OsmValidator;
032import org.openstreetmap.josm.data.validation.Severity;
033import org.openstreetmap.josm.data.validation.Test;
034import org.openstreetmap.josm.data.validation.TestError;
035import org.openstreetmap.josm.gui.DefaultNameFormatter;
036import org.openstreetmap.josm.gui.mappaint.ElemStyles;
037import org.openstreetmap.josm.gui.mappaint.MapPaintStyles;
038import org.openstreetmap.josm.gui.mappaint.styleelement.AreaElement;
039import org.openstreetmap.josm.gui.progress.ProgressMonitor;
040import org.openstreetmap.josm.tools.Pair;
041
042/**
043 * Checks if multipolygons are valid
044 * @since 3669
045 */
046public class MultipolygonTest extends Test {
047
048    /** Non-Way in multipolygon */
049    public static final int WRONG_MEMBER_TYPE = 1601;
050    /** No useful role for multipolygon member */
051    public static final int WRONG_MEMBER_ROLE = 1602;
052    /** Multipolygon is not closed */
053    public static final int NON_CLOSED_WAY = 1603;
054    /** No outer way for multipolygon */
055    public static final int MISSING_OUTER_WAY = 1604;
056    /** Multipolygon inner way is outside */
057    public static final int INNER_WAY_OUTSIDE = 1605;
058    /** Intersection between multipolygon ways */
059    public static final int CROSSING_WAYS = 1606;
060    /** Style for outer way mismatches / With the currently used mappaint style(s) the style for outer way mismatches the area style */
061    public static final int OUTER_STYLE_MISMATCH = 1607;
062    /** With the currently used mappaint style the style for inner way equals the multipolygon style */
063    public static final int INNER_STYLE_MISMATCH = 1608;
064    /** Area style way is not closed */
065    public static final int NOT_CLOSED = 1609;
066    /** No area style for multipolygon */
067    public static final int NO_STYLE = 1610;
068    /** Multipolygon relation should be tagged with area tags and not the outer way(s) */
069    public static final int NO_STYLE_POLYGON = 1611;
070    /** Area style on outer way */
071    public static final int OUTER_STYLE = 1613;
072    /** Multipolygon member repeated (same primitive, same role */
073    public static final int REPEATED_MEMBER_SAME_ROLE = 1614;
074    /** Multipolygon member repeated (same primitive, different role) */
075    public static final int REPEATED_MEMBER_DIFF_ROLE = 1615;
076
077    private static volatile ElemStyles styles;
078
079    private final Set<String> keysCheckedByAnotherTest = new HashSet<>();
080
081    /**
082     * Constructs a new {@code MultipolygonTest}.
083     */
084    public MultipolygonTest() {
085        super(tr("Multipolygon"),
086                tr("This test checks if multipolygons are valid."));
087    }
088
089    @Override
090    public void initialize() {
091        styles = MapPaintStyles.getStyles();
092    }
093
094    @Override
095    public void startTest(ProgressMonitor progressMonitor) {
096        super.startTest(progressMonitor);
097        keysCheckedByAnotherTest.clear();
098        for (Test t : OsmValidator.getEnabledTests(false)) {
099            if (t instanceof UnclosedWays) {
100                keysCheckedByAnotherTest.addAll(((UnclosedWays) t).getCheckedKeys());
101                break;
102            }
103        }
104    }
105
106    @Override
107    public void endTest() {
108        keysCheckedByAnotherTest.clear();
109        super.endTest();
110    }
111
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
146    @Override
147    public void visit(Way w) {
148        if (!w.isArea() && ElemStyles.hasOnlyAreaElemStyle(w)) {
149            List<Node> nodes = w.getNodes();
150            if (nodes.isEmpty()) return; // fix zero nodes bug
151            for (String key : keysCheckedByAnotherTest) {
152                if (w.hasKey(key)) {
153                    return;
154                }
155            }
156            errors.add(TestError.builder(this, Severity.WARNING, NOT_CLOSED)
157                    .message(tr("Area style way is not closed"))
158                    .primitives(w)
159                    .highlight(Arrays.asList(nodes.get(0), nodes.get(nodes.size() - 1)))
160                    .build());
161        }
162    }
163
164    @Override
165    public void visit(Relation r) {
166        if (r.isMultipolygon()) {
167            checkMembersAndRoles(r);
168            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);
179            }
180        }
181    }
182
183    /**
184     * Checks that multipolygon has at least an outer way:<ul>
185     * <li>{@link #MISSING_OUTER_WAY}: No outer way for multipolygon</li>
186     * </ul>
187     * @param r relation
188     */
189    private void checkOuterWay(Relation r) {
190        boolean hasOuterWay = false;
191        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        }
230    }
231
232    /**
233     * Various style-related checks:<ul>
234     * <li>{@link #NO_STYLE_POLYGON}: Multipolygon relation should be tagged with area tags and not the outer way</li>
235     * <li>{@link #INNER_STYLE_MISMATCH}: With the currently used mappaint style the style for inner way equals the multipolygon style</li>
236     * <li>{@link #OUTER_STYLE_MISMATCH}: Style for outer way mismatches</li>
237     * <li>{@link #OUTER_STYLE}: Area style on outer way</li>
238     * </ul>
239     * @param r relation
240     * @param polygon multipolygon
241     */
242    private void checkStyleConsistency(Relation r, Multipolygon polygon) {
243        if (styles != null && !"boundary".equals(r.get("type"))) {
244            AreaElement area = ElemStyles.getAreaElemStyle(r, false);
245            boolean areaStyle = area != null;
246            // If area style was not found for relation then use style of ways
247            if (area == null) {
248                for (Way w : polygon.getOuterWays()) {
249                    area = ElemStyles.getAreaElemStyle(w, true);
250                    if (area != null) {
251                        break;
252                    }
253                }
254                if (area == null) {
255                    errors.add(TestError.builder(this, Severity.OTHER, NO_STYLE)
256                            .message(tr("No area style for multipolygon"))
257                            .primitives(r)
258                            .build());
259                } else {
260                    /* old style multipolygon - solve: copy tags from outer way to multipolygon */
261                    errors.add(TestError.builder(this, Severity.WARNING, NO_STYLE_POLYGON)
262                            .message(trn("Multipolygon relation should be tagged with area tags and not the outer way",
263                                    "Multipolygon relation should be tagged with area tags and not the outer ways",
264                                    polygon.getOuterWays().size()))
265                            .primitives(r)
266                            .build());
267                }
268            }
269
270            if (area != null) {
271                for (Way wInner : polygon.getInnerWays()) {
272                    AreaElement areaInner = ElemStyles.getAreaElemStyle(wInner, false);
273
274                    if (areaInner != null && area.equals(areaInner)) {
275                        errors.add(TestError.builder(this, Severity.OTHER, INNER_STYLE_MISMATCH)
276                                .message(tr("With the currently used mappaint style the style for inner way equals the multipolygon style"))
277                                .primitives(addRelationIfNeeded(r, wInner))
278                                .highlight(wInner)
279                                .build());
280                    }
281                }
282                for (Way wOuter : polygon.getOuterWays()) {
283                    AreaElement areaOuter = ElemStyles.getAreaElemStyle(wOuter, false);
284                    if (areaOuter != null) {
285                        if (!area.equals(areaOuter)) {
286                            String message = !areaStyle ? tr("Style for outer way mismatches")
287                                    : tr("With the currently used mappaint style(s) the style for outer way mismatches the area style");
288                            errors.add(TestError.builder(this, Severity.OTHER, OUTER_STYLE_MISMATCH)
289                                    .message(message)
290                                    .primitives(addRelationIfNeeded(r, wOuter))
291                                    .highlight(wOuter)
292                                    .build());
293                        } else if (areaStyle) { /* style on outer way of multipolygon, but equal to polygon */
294                            errors.add(TestError.builder(this, Severity.WARNING, OUTER_STYLE)
295                                    .message(tr("Area style on outer way"))
296                                    .primitives(addRelationIfNeeded(r, wOuter))
297                                    .highlight(wOuter)
298                                    .build());
299                        }
300                    }
301                }
302            }
303        }
304    }
305
306    /**
307     * Various geometry-related checks:<ul>
308     * <li>{@link #NON_CLOSED_WAY}: Multipolygon is not closed</li>
309     * <li>{@link #INNER_WAY_OUTSIDE}: Multipolygon inner way is outside</li>
310     * <li>{@link #CROSSING_WAYS}: Intersection between multipolygon ways</li>
311     * </ul>
312     * @param r relation
313     * @param polygon multipolygon
314     */
315    private void checkGeometry(Relation r, Multipolygon polygon) {
316        List<Node> openNodes = polygon.getOpenEnds();
317        if (!openNodes.isEmpty()) {
318            errors.add(TestError.builder(this, Severity.WARNING, NON_CLOSED_WAY)
319                    .message(tr("Multipolygon is not closed"))
320                    .primitives(addRelationIfNeeded(r, openNodes))
321                    .highlight(openNodes)
322                    .build());
323        }
324
325        // For painting is used Polygon class which works with ints only. For validation we need more precision
326        List<PolyData> innerPolygons = polygon.getInnerPolygons();
327        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()))
353                        .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()))
367                        .build());
368            }
369        }
370        return intersection;
371    }
372
373    /**
374     * Check for:<ul>
375     * <li>{@link #WRONG_MEMBER_ROLE}: No useful role for multipolygon member</li>
376     * <li>{@link #WRONG_MEMBER_TYPE}: Non-Way in multipolygon</li>
377     * </ul>
378     * @param r relation
379     */
380    private void checkMembersAndRoles(Relation r) {
381        for (RelationMember rm : r.getMembers()) {
382            if (rm.isWay()) {
383                if (!(rm.hasRole("inner", "outer") || !rm.hasRole())) {
384                    errors.add(TestError.builder(this, Severity.WARNING, WRONG_MEMBER_ROLE)
385                            .message(tr("No useful role for multipolygon member"))
386                            .primitives(addRelationIfNeeded(r, rm.getMember()))
387                            .build());
388                }
389            } else {
390                if (!rm.hasRole("admin_centre", "label", "subarea", "land_area")) {
391                    errors.add(TestError.builder(this, Severity.WARNING, WRONG_MEMBER_TYPE)
392                            .message(tr("Non-Way in multipolygon"))
393                            .primitives(addRelationIfNeeded(r, rm.getMember()))
394                            .build());
395                }
396            }
397        }
398    }
399
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) {
405        // add multipolygon in order to let user select something and fix the error
406        if (!primitives.contains(r)) {
407            // Diamond operator does not work with Java 9 here
408            @SuppressWarnings("unused")
409            List<OsmPrimitive> newPrimitives = new ArrayList<OsmPrimitive>(primitives);
410            newPrimitives.add(0, r);
411            return newPrimitives;
412        } else {
413            return primitives;
414        }
415    }
416
417    /**
418     * Check for:<ul>
419     * <li>{@link #REPEATED_MEMBER_DIFF_ROLE}: Multipolygon member(s) repeated with different role</li>
420     * <li>{@link #REPEATED_MEMBER_SAME_ROLE}: Multipolygon member(s) repeated with same role</li>
421     * </ul>
422     * @param r relation
423     * @return true if repeated members have been detected, false otherwise
424     */
425    private boolean checkRepeatedWayMembers(Relation r) {
426        boolean hasDups = false;
427        Map<OsmPrimitive, List<RelationMember>> seenMemberPrimitives = new HashMap<>();
428        for (RelationMember rm : r.getMembers()) {
429            List<RelationMember> list = seenMemberPrimitives.get(rm.getMember());
430            if (list == null) {
431                list = new ArrayList<>(2);
432                seenMemberPrimitives.put(rm.getMember(), list);
433            } else {
434                hasDups = true;
435            }
436            list.add(rm);
437        }
438        if (hasDups) {
439            List<OsmPrimitive> repeatedSameRole = new ArrayList<>();
440            List<OsmPrimitive> repeatedDiffRole = new ArrayList<>();
441            for (Entry<OsmPrimitive, List<RelationMember>> e : seenMemberPrimitives.entrySet()) {
442                List<RelationMember> visited = e.getValue();
443                if (e.getValue().size() == 1)
444                    continue;
445                // we found a duplicate member, check if the roles differ
446                boolean rolesDiffer = false;
447                RelationMember rm = visited.get(0);
448                List<OsmPrimitive> primitives = new ArrayList<>();
449                for (int i = 1; i < visited.size(); i++) {
450                    RelationMember v = visited.get(i);
451                    primitives.add(rm.getMember());
452                    if (!v.getRole().equals(rm.getRole())) {
453                        rolesDiffer = true;
454                    }
455                }
456                if (rolesDiffer) {
457                    repeatedDiffRole.addAll(primitives);
458                } else {
459                    repeatedSameRole.addAll(primitives);
460                }
461            }
462            addRepeatedMemberError(r, repeatedDiffRole, REPEATED_MEMBER_DIFF_ROLE, tr("Multipolygon member(s) repeated with different role"));
463            addRepeatedMemberError(r, repeatedSameRole, REPEATED_MEMBER_SAME_ROLE, tr("Multipolygon member(s) repeated with same role"));
464        }
465        return hasDups;
466    }
467
468    private void addRepeatedMemberError(Relation r, List<OsmPrimitive> repeatedMembers, int errorCode, String msg) {
469        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)
474                    .message(msg)
475                    .primitives(prims)
476                    .highlight(repeatedMembers)
477                    .build());
478        }
479    }
480
481    @Override
482    public Command fixError(TestError testError) {
483        if (testError.getCode() == REPEATED_MEMBER_SAME_ROLE) {
484            ArrayList<OsmPrimitive> primitives = new ArrayList<>(testError.getPrimitives());
485            if (primitives.size() >= 2 && primitives.get(0) instanceof Relation) {
486                Relation oldRel = (Relation) primitives.get(0);
487                Relation newRel = new Relation(oldRel);
488                List<OsmPrimitive> repeatedPrims = primitives.subList(1, primitives.size());
489                List<RelationMember> oldMembers = oldRel.getMembers();
490
491                List<RelationMember> newMembers = new ArrayList<>();
492                HashSet<OsmPrimitive> toRemove = new HashSet<>(repeatedPrims);
493                HashSet<OsmPrimitive> found = new HashSet<>(repeatedPrims.size());
494                for (RelationMember rm : oldMembers) {
495                    if (toRemove.contains(rm.getMember())) {
496                        if (!found.contains(rm.getMember())) {
497                            found.add(rm.getMember());
498                            newMembers.add(rm);
499                        }
500                    } else {
501                        newMembers.add(rm);
502                    }
503                }
504                newRel.setMembers(newMembers);
505                return new ChangeCommand(oldRel, newRel);
506            }
507        }
508        return null;
509    }
510
511    @Override
512    public boolean isFixable(TestError testError) {
513        if (testError.getCode() == REPEATED_MEMBER_SAME_ROLE)
514            return true;
515        return false;
516    }
517}