001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data.validation.tests;
003
004import static org.openstreetmap.josm.tools.I18n.tr;
005import static org.openstreetmap.josm.tools.I18n.trn;
006
007import java.awt.geom.GeneralPath;
008import java.text.MessageFormat;
009import java.util.ArrayList;
010import java.util.Arrays;
011import java.util.Collection;
012import java.util.Collections;
013import java.util.HashSet;
014import java.util.LinkedList;
015import java.util.List;
016import java.util.Set;
017
018import org.openstreetmap.josm.Main;
019import org.openstreetmap.josm.actions.CreateMultipolygonAction;
020import org.openstreetmap.josm.data.osm.Node;
021import org.openstreetmap.josm.data.osm.OsmPrimitive;
022import org.openstreetmap.josm.data.osm.Relation;
023import org.openstreetmap.josm.data.osm.RelationMember;
024import org.openstreetmap.josm.data.osm.Way;
025import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon;
026import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.PolyData;
027import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.PolyData.Intersection;
028import org.openstreetmap.josm.data.osm.visitor.paint.relations.MultipolygonCache;
029import org.openstreetmap.josm.data.validation.OsmValidator;
030import org.openstreetmap.josm.data.validation.Severity;
031import org.openstreetmap.josm.data.validation.Test;
032import org.openstreetmap.josm.data.validation.TestError;
033import org.openstreetmap.josm.gui.DefaultNameFormatter;
034import org.openstreetmap.josm.gui.mappaint.ElemStyles;
035import org.openstreetmap.josm.gui.mappaint.MapPaintStyles;
036import org.openstreetmap.josm.gui.mappaint.styleelement.AreaElement;
037import org.openstreetmap.josm.gui.progress.ProgressMonitor;
038import org.openstreetmap.josm.tools.Pair;
039
040/**
041 * Checks if multipolygons are valid
042 * @since 3669
043 */
044public class MultipolygonTest extends Test {
045
046    /** Non-Way in multipolygon */
047    public static final int WRONG_MEMBER_TYPE = 1601;
048    /** No useful role for multipolygon member */
049    public static final int WRONG_MEMBER_ROLE = 1602;
050    /** Multipolygon is not closed */
051    public static final int NON_CLOSED_WAY = 1603;
052    /** No outer way for multipolygon */
053    public static final int MISSING_OUTER_WAY = 1604;
054    /** Multipolygon inner way is outside */
055    public static final int INNER_WAY_OUTSIDE = 1605;
056    /** Intersection between multipolygon ways */
057    public static final int CROSSING_WAYS = 1606;
058    /** Style for outer way mismatches / With the currently used mappaint style(s) the style for outer way mismatches the area style */
059    public static final int OUTER_STYLE_MISMATCH = 1607;
060    /** With the currently used mappaint style the style for inner way equals the multipolygon style */
061    public static final int INNER_STYLE_MISMATCH = 1608;
062    /** Area style way is not closed */
063    public static final int NOT_CLOSED = 1609;
064    /** No area style for multipolygon */
065    public static final int NO_STYLE = 1610;
066    /** Multipolygon relation should be tagged with area tags and not the outer way(s) */
067    public static final int NO_STYLE_POLYGON = 1611;
068    /** Area style on outer way */
069    public static final int OUTER_STYLE = 1613;
070
071    private static volatile ElemStyles styles;
072
073    private final Set<String> keysCheckedByAnotherTest = new HashSet<>();
074
075    /**
076     * Constructs a new {@code MultipolygonTest}.
077     */
078    public MultipolygonTest() {
079        super(tr("Multipolygon"),
080                tr("This test checks if multipolygons are valid."));
081    }
082
083    @Override
084    public void initialize() {
085        styles = MapPaintStyles.getStyles();
086    }
087
088    @Override
089    public void startTest(ProgressMonitor progressMonitor) {
090        super.startTest(progressMonitor);
091        keysCheckedByAnotherTest.clear();
092        for (Test t : OsmValidator.getEnabledTests(false)) {
093            if (t instanceof UnclosedWays) {
094                keysCheckedByAnotherTest.addAll(((UnclosedWays) t).getCheckedKeys());
095                break;
096            }
097        }
098    }
099
100    @Override
101    public void endTest() {
102        keysCheckedByAnotherTest.clear();
103        super.endTest();
104    }
105
106    private static GeneralPath createPath(List<Node> nodes) {
107        GeneralPath result = new GeneralPath();
108        result.moveTo((float) nodes.get(0).getCoor().lat(), (float) nodes.get(0).getCoor().lon());
109        for (int i = 1; i < nodes.size(); i++) {
110            Node n = nodes.get(i);
111            result.lineTo((float) n.getCoor().lat(), (float) n.getCoor().lon());
112        }
113        return result;
114    }
115
116    private static List<GeneralPath> createPolygons(List<Multipolygon.PolyData> joinedWays) {
117        List<GeneralPath> result = new ArrayList<>();
118        for (Multipolygon.PolyData way : joinedWays) {
119            result.add(createPath(way.getNodes()));
120        }
121        return result;
122    }
123
124    private static Intersection getPolygonIntersection(GeneralPath outer, List<Node> inner) {
125        boolean inside = false;
126        boolean outside = false;
127
128        for (Node n : inner) {
129            boolean contains = outer.contains(n.getCoor().lat(), n.getCoor().lon());
130            inside = inside | contains;
131            outside = outside | !contains;
132            if (inside & outside) {
133                return Intersection.CROSSING;
134            }
135        }
136
137        return inside ? Intersection.INSIDE : Intersection.OUTSIDE;
138    }
139
140    @Override
141    public void visit(Way w) {
142        if (!w.isArea() && ElemStyles.hasOnlyAreaElemStyle(w)) {
143            List<Node> nodes = w.getNodes();
144            if (nodes.isEmpty()) return; // fix zero nodes bug
145            for (String key : keysCheckedByAnotherTest) {
146                if (w.hasKey(key)) {
147                    return;
148                }
149            }
150            errors.add(new TestError(this, Severity.WARNING, tr("Area style way is not closed"), NOT_CLOSED,
151                    Collections.singletonList(w), Arrays.asList(nodes.get(0), nodes.get(nodes.size() - 1))));
152        }
153    }
154
155    @Override
156    public void visit(Relation r) {
157        if (r.isMultipolygon()) {
158            checkMembersAndRoles(r);
159            checkOuterWay(r);
160
161            // Rest of checks is only for complete multipolygons
162            if (!r.hasIncompleteMembers()) {
163                Multipolygon polygon = MultipolygonCache.getInstance().get(Main.map.mapView, r);
164
165                // Create new multipolygon using the logics from CreateMultipolygonAction and see if roles match.
166                checkMemberRoleCorrectness(r);
167                checkStyleConsistency(r, polygon);
168                checkGeometry(r, polygon);
169            }
170        }
171    }
172
173    /**
174     * Checks that multipolygon has at least an outer way:<ul>
175     * <li>{@link #MISSING_OUTER_WAY}: No outer way for multipolygon</li>
176     * </ul>
177     * @param r relation
178     */
179    private void checkOuterWay(Relation r) {
180        boolean hasOuterWay = false;
181        for (RelationMember m : r.getMembers()) {
182            if ("outer".equals(m.getRole())) {
183                hasOuterWay = true;
184                break;
185            }
186        }
187        if (!hasOuterWay) {
188            addError(r, new TestError(this, Severity.WARNING, tr("No outer way for multipolygon"), MISSING_OUTER_WAY, r));
189        }
190    }
191
192    /**
193     * Create new multipolygon using the logics from CreateMultipolygonAction and see if roles match:<ul>
194     * <li>{@link #WRONG_MEMBER_ROLE}: Role for ''{0}'' should be ''{1}''</li>
195     * </ul>
196     * @param r relation
197     */
198    private void checkMemberRoleCorrectness(Relation r) {
199        final Pair<Relation, Relation> newMP = CreateMultipolygonAction.createMultipolygonRelation(r.getMemberPrimitives(Way.class), false);
200        if (newMP != null) {
201            for (RelationMember member : r.getMembers()) {
202                final Collection<RelationMember> memberInNewMP = newMP.b.getMembersFor(Collections.singleton(member.getMember()));
203                if (memberInNewMP != null && !memberInNewMP.isEmpty()) {
204                    final String roleInNewMP = memberInNewMP.iterator().next().getRole();
205                    if (!member.getRole().equals(roleInNewMP)) {
206                        List<OsmPrimitive> l = new ArrayList<>();
207                        l.add(r);
208                        l.add(member.getMember());
209                        addError(r, new TestError(this, Severity.WARNING, RelationChecker.ROLE_VERIF_PROBLEM_MSG,
210                                tr("Role for ''{0}'' should be ''{1}''",
211                                        member.getMember().getDisplayName(DefaultNameFormatter.getInstance()), roleInNewMP),
212                                MessageFormat.format("Role for ''{0}'' should be ''{1}''",
213                                        member.getMember().getDisplayName(DefaultNameFormatter.getInstance()), roleInNewMP),
214                                WRONG_MEMBER_ROLE, l, Collections.singleton(member.getMember())));
215                    }
216                }
217            }
218        }
219    }
220
221    /**
222     * Various style-related checks:<ul>
223     * <li>{@link #NO_STYLE_POLYGON}: Multipolygon relation should be tagged with area tags and not the outer way</li>
224     * <li>{@link #INNER_STYLE_MISMATCH}: With the currently used mappaint style the style for inner way equals the multipolygon style</li>
225     * <li>{@link #OUTER_STYLE_MISMATCH}: Style for outer way mismatches</li>
226     * <li>{@link #OUTER_STYLE}: Area style on outer way</li>
227     * </ul>
228     * @param r relation
229     * @param polygon multipolygon
230     */
231    private void checkStyleConsistency(Relation r, Multipolygon polygon) {
232        if (styles != null && !"boundary".equals(r.get("type"))) {
233            AreaElement area = ElemStyles.getAreaElemStyle(r, false);
234            boolean areaStyle = area != null;
235            // If area style was not found for relation then use style of ways
236            if (area == null) {
237                for (Way w : polygon.getOuterWays()) {
238                    area = ElemStyles.getAreaElemStyle(w, true);
239                    if (area != null) {
240                        break;
241                    }
242                }
243                if (area == null) {
244                    addError(r, new TestError(this, Severity.OTHER, tr("No area style for multipolygon"), NO_STYLE, r));
245                } else {
246                    /* old style multipolygon - solve: copy tags from outer way to multipolygon */
247                    addError(r, new TestError(this, Severity.WARNING,
248                            trn("Multipolygon relation should be tagged with area tags and not the outer way",
249                                    "Multipolygon relation should be tagged with area tags and not the outer ways",
250                                    polygon.getOuterWays().size()),
251                       NO_STYLE_POLYGON, r));
252                }
253            }
254
255            if (area != null) {
256                for (Way wInner : polygon.getInnerWays()) {
257                    AreaElement areaInner = ElemStyles.getAreaElemStyle(wInner, false);
258
259                    if (areaInner != null && area.equals(areaInner)) {
260                        List<OsmPrimitive> l = new ArrayList<>();
261                        l.add(r);
262                        l.add(wInner);
263                        addError(r, new TestError(this, Severity.OTHER,
264                                tr("With the currently used mappaint style the style for inner way equals the multipolygon style"),
265                                INNER_STYLE_MISMATCH, l, Collections.singletonList(wInner)));
266                    }
267                }
268                for (Way wOuter : polygon.getOuterWays()) {
269                    AreaElement areaOuter = ElemStyles.getAreaElemStyle(wOuter, false);
270                    if (areaOuter != null) {
271                        List<OsmPrimitive> l = new ArrayList<>();
272                        l.add(r);
273                        l.add(wOuter);
274                        if (!area.equals(areaOuter)) {
275                            addError(r, new TestError(this, Severity.OTHER, !areaStyle ? tr("Style for outer way mismatches")
276                            : tr("With the currently used mappaint style(s) the style for outer way mismatches the area style"),
277                            OUTER_STYLE_MISMATCH, l, Collections.singletonList(wOuter)));
278                        } else if (areaStyle) { /* style on outer way of multipolygon, but equal to polygon */
279                            addError(r, new TestError(this, Severity.WARNING, tr("Area style on outer way"), OUTER_STYLE,
280                            l, Collections.singletonList(wOuter)));
281                        }
282                    }
283                }
284            }
285        }
286    }
287
288    /**
289     * Various geometry-related checks:<ul>
290     * <li>{@link #NON_CLOSED_WAY}: Multipolygon is not closed</li>
291     * <li>{@link #INNER_WAY_OUTSIDE}: Multipolygon inner way is outside</li>
292     * <li>{@link #CROSSING_WAYS}: Intersection between multipolygon ways</li>
293     * </ul>
294     * @param r relation
295     * @param polygon multipolygon
296     */
297    private void checkGeometry(Relation r, Multipolygon polygon) {
298        List<Node> openNodes = polygon.getOpenEnds();
299        if (!openNodes.isEmpty()) {
300            List<OsmPrimitive> primitives = new LinkedList<>();
301            primitives.add(r);
302            primitives.addAll(openNodes);
303            addError(r, new TestError(this, Severity.WARNING, tr("Multipolygon is not closed"), NON_CLOSED_WAY, primitives, openNodes));
304        }
305
306        // For painting is used Polygon class which works with ints only. For validation we need more precision
307        List<PolyData> innerPolygons = polygon.getInnerPolygons();
308        List<PolyData> outerPolygons = polygon.getOuterPolygons();
309        List<GeneralPath> innerPolygonsPaths = innerPolygons.isEmpty() ? Collections.<GeneralPath>emptyList() : createPolygons(innerPolygons);
310        List<GeneralPath> outerPolygonsPaths = createPolygons(outerPolygons);
311        for (int i = 0; i < outerPolygons.size(); i++) {
312            PolyData pdOuter = outerPolygons.get(i);
313            // Check for intersection between outer members
314            for (int j = i+1; j < outerPolygons.size(); j++) {
315                checkCrossingWays(r, outerPolygons, outerPolygonsPaths, pdOuter, j);
316            }
317        }
318        for (int i = 0; i < innerPolygons.size(); i++) {
319            PolyData pdInner = innerPolygons.get(i);
320            // Check for intersection between inner members
321            for (int j = i+1; j < innerPolygons.size(); j++) {
322                checkCrossingWays(r, innerPolygons, innerPolygonsPaths, pdInner, j);
323            }
324            // Check for intersection between inner and outer members
325            boolean outside = true;
326            for (int o = 0; o < outerPolygons.size(); o++) {
327                outside &= checkCrossingWays(r, outerPolygons, outerPolygonsPaths, pdInner, o) == Intersection.OUTSIDE;
328            }
329            if (outside) {
330                addError(r, new TestError(this, Severity.WARNING, tr("Multipolygon inner way is outside"),
331                        INNER_WAY_OUTSIDE, Collections.singletonList(r), Arrays.asList(pdInner.getNodes())));
332            }
333        }
334    }
335
336    private Intersection checkCrossingWays(Relation r, List<PolyData> polygons, List<GeneralPath> polygonsPaths, PolyData pd, int idx) {
337        Intersection intersection = getPolygonIntersection(polygonsPaths.get(idx), pd.getNodes());
338        if (intersection == Intersection.CROSSING) {
339            PolyData pdOther = polygons.get(idx);
340            if (pdOther != null) {
341                addError(r, new TestError(this, Severity.WARNING, tr("Intersection between multipolygon ways"),
342                        CROSSING_WAYS, Collections.singletonList(r), Arrays.asList(pd.getNodes(), pdOther.getNodes())));
343            }
344        }
345        return intersection;
346    }
347
348    /**
349     * Check for:<ul>
350     * <li>{@link #WRONG_MEMBER_ROLE}: No useful role for multipolygon member</li>
351     * <li>{@link #WRONG_MEMBER_TYPE}: Non-Way in multipolygon</li>
352     * </ul>
353     * @param r relation
354     */
355    private void checkMembersAndRoles(Relation r) {
356        for (RelationMember rm : r.getMembers()) {
357            if (rm.isWay()) {
358                if (!(rm.hasRole("inner", "outer") || !rm.hasRole())) {
359                    addError(r, new TestError(this, Severity.WARNING, tr("No useful role for multipolygon member"),
360                            WRONG_MEMBER_ROLE, rm.getMember()));
361                }
362            } else {
363                if (!rm.hasRole("admin_centre", "label", "subarea", "land_area")) {
364                    addError(r, new TestError(this, Severity.WARNING, tr("Non-Way in multipolygon"), WRONG_MEMBER_TYPE, rm.getMember()));
365                }
366            }
367        }
368    }
369
370    private static void addRelationIfNeeded(TestError error, Relation r) {
371        // Fix #8212 : if the error references only incomplete primitives,
372        // add multipolygon in order to let user select something and fix the error
373        Collection<? extends OsmPrimitive> primitives = error.getPrimitives();
374        if (!primitives.contains(r)) {
375            for (OsmPrimitive p : primitives) {
376                if (!p.isIncomplete()) {
377                    return;
378                }
379            }
380            // Diamond operator does not work with Java 9 here
381            @SuppressWarnings("unused")
382            List<OsmPrimitive> newPrimitives = new ArrayList<OsmPrimitive>(primitives);
383            newPrimitives.add(0, r);
384            error.setPrimitives(newPrimitives);
385        }
386    }
387
388    private void addError(Relation r, TestError error) {
389        addRelationIfNeeded(error, r);
390        errors.add(error);
391    }
392}