001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data.osm.visitor.paint.relations;
003
004import java.awt.geom.Path2D;
005import java.awt.geom.PathIterator;
006import java.awt.geom.Rectangle2D;
007import java.util.ArrayList;
008import java.util.Collection;
009import java.util.Collections;
010import java.util.HashSet;
011import java.util.Iterator;
012import java.util.List;
013import java.util.Set;
014
015import org.openstreetmap.josm.Main;
016import org.openstreetmap.josm.data.Preferences.PreferenceChangeEvent;
017import org.openstreetmap.josm.data.Preferences.PreferenceChangedListener;
018import org.openstreetmap.josm.data.coor.EastNorth;
019import org.openstreetmap.josm.data.osm.DataSet;
020import org.openstreetmap.josm.data.osm.Node;
021import org.openstreetmap.josm.data.osm.OsmPrimitiveType;
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.event.NodeMovedEvent;
026import org.openstreetmap.josm.data.osm.event.WayNodesChangedEvent;
027import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.PolyData.Intersection;
028import org.openstreetmap.josm.data.projection.Projection;
029import org.openstreetmap.josm.tools.Geometry;
030import org.openstreetmap.josm.tools.Geometry.AreaAndPerimeter;
031
032/**
033 * Multipolygon data used to represent complex areas, see <a href="https://wiki.openstreetmap.org/wiki/Relation:multipolygon">wiki</a>.
034 * @since 2788
035 */
036public class Multipolygon {
037
038    /** preference key for a collection of roles which indicate that the respective member belongs to an
039     * <em>outer</em> polygon. Default is <tt>outer</tt>.
040     */
041    public static final String PREF_KEY_OUTER_ROLES = "mappaint.multipolygon.outer.roles";
042
043    /** preference key for collection of role prefixes which indicate that the respective
044     *  member belongs to an <em>outer</em> polygon. Default is empty.
045     */
046    public static final String PREF_KEY_OUTER_ROLE_PREFIXES = "mappaint.multipolygon.outer.role-prefixes";
047
048    /** preference key for a collection of roles which indicate that the respective member belongs to an
049     * <em>inner</em> polygon. Default is <tt>inner</tt>.
050     */
051    public static final String PREF_KEY_INNER_ROLES = "mappaint.multipolygon.inner.roles";
052
053    /** preference key for collection of role prefixes which indicate that the respective
054     *  member belongs to an <em>inner</em> polygon. Default is empty.
055     */
056    public static final String PREF_KEY_INNER_ROLE_PREFIXES = "mappaint.multipolygon.inner.role-prefixes";
057
058    /**
059     * <p>Kind of strategy object which is responsible for deciding whether a given
060     * member role indicates that the member belongs to an <em>outer</em> or an
061     * <em>inner</em> polygon.</p>
062     *
063     * <p>The decision is taken based on preference settings, see the four preference keys
064     * above.</p>
065     */
066    private static class MultipolygonRoleMatcher implements PreferenceChangedListener {
067        private final List<String> outerExactRoles = new ArrayList<>();
068        private final List<String> outerRolePrefixes = new ArrayList<>();
069        private final List<String> innerExactRoles = new ArrayList<>();
070        private final List<String> innerRolePrefixes = new ArrayList<>();
071
072        private void initDefaults() {
073            outerExactRoles.clear();
074            outerRolePrefixes.clear();
075            innerExactRoles.clear();
076            innerRolePrefixes.clear();
077            outerExactRoles.add("outer");
078            innerExactRoles.add("inner");
079        }
080
081        private static void setNormalized(Collection<String> literals, List<String> target) {
082            target.clear();
083            for (String l: literals) {
084                if (l == null) {
085                    continue;
086                }
087                l = l.trim();
088                if (!target.contains(l)) {
089                    target.add(l);
090                }
091            }
092        }
093
094        private void initFromPreferences() {
095            initDefaults();
096            if (Main.pref == null) return;
097            Collection<String> literals;
098            literals = Main.pref.getCollection(PREF_KEY_OUTER_ROLES);
099            if (literals != null && !literals.isEmpty()) {
100                setNormalized(literals, outerExactRoles);
101            }
102            literals = Main.pref.getCollection(PREF_KEY_OUTER_ROLE_PREFIXES);
103            if (literals != null && !literals.isEmpty()) {
104                setNormalized(literals, outerRolePrefixes);
105            }
106            literals = Main.pref.getCollection(PREF_KEY_INNER_ROLES);
107            if (literals != null && !literals.isEmpty()) {
108                setNormalized(literals, innerExactRoles);
109            }
110            literals = Main.pref.getCollection(PREF_KEY_INNER_ROLE_PREFIXES);
111            if (literals != null && !literals.isEmpty()) {
112                setNormalized(literals, innerRolePrefixes);
113            }
114        }
115
116        @Override
117        public void preferenceChanged(PreferenceChangeEvent evt) {
118            if (PREF_KEY_INNER_ROLE_PREFIXES.equals(evt.getKey()) ||
119                    PREF_KEY_INNER_ROLES.equals(evt.getKey()) ||
120                    PREF_KEY_OUTER_ROLE_PREFIXES.equals(evt.getKey()) ||
121                    PREF_KEY_OUTER_ROLES.equals(evt.getKey())) {
122                initFromPreferences();
123            }
124        }
125
126        boolean isOuterRole(String role) {
127            if (role == null) return false;
128            for (String candidate: outerExactRoles) {
129                if (role.equals(candidate)) return true;
130            }
131            for (String candidate: outerRolePrefixes) {
132                if (role.startsWith(candidate)) return true;
133            }
134            return false;
135        }
136
137        boolean isInnerRole(String role) {
138            if (role == null) return false;
139            for (String candidate: innerExactRoles) {
140                if (role.equals(candidate)) return true;
141            }
142            for (String candidate: innerRolePrefixes) {
143                if (role.startsWith(candidate)) return true;
144            }
145            return false;
146        }
147    }
148
149    /*
150     * Init a private global matcher object which will listen to preference changes.
151     */
152    private static MultipolygonRoleMatcher roleMatcher;
153
154    private static synchronized MultipolygonRoleMatcher getMultipolygonRoleMatcher() {
155        if (roleMatcher == null) {
156            roleMatcher = new MultipolygonRoleMatcher();
157            if (Main.pref != null) {
158                roleMatcher.initFromPreferences();
159                Main.pref.addPreferenceChangeListener(roleMatcher);
160            }
161        }
162        return roleMatcher;
163    }
164
165    /**
166     * Class representing a string of ways.
167     *
168     * The last node of one way is the first way of the next one.
169     * The string may or may not be closed.
170     */
171    public static class JoinedWay {
172        protected final List<Node> nodes;
173        protected final Collection<Long> wayIds;
174        protected boolean selected;
175
176        /**
177         * Constructs a new {@code JoinedWay}.
178         * @param nodes list of nodes - must not be null
179         * @param wayIds list of way IDs - must not be null
180         * @param selected whether joined way is selected or not
181         */
182        public JoinedWay(List<Node> nodes, Collection<Long> wayIds, boolean selected) {
183            this.nodes = new ArrayList<>(nodes);
184            this.wayIds = new ArrayList<>(wayIds);
185            this.selected = selected;
186        }
187
188        /**
189         * Replies the list of nodes.
190         * @return the list of nodes
191         */
192        public List<Node> getNodes() {
193            return Collections.unmodifiableList(nodes);
194        }
195
196        /**
197         * Replies the list of way IDs.
198         * @return the list of way IDs
199         */
200        public Collection<Long> getWayIds() {
201            return Collections.unmodifiableCollection(wayIds);
202        }
203
204        /**
205         * Determines if this is selected.
206         * @return {@code true} if this is selected
207         */
208        public final boolean isSelected() {
209            return selected;
210        }
211
212        /**
213         * Sets whether this is selected
214         * @param selected {@code true} if this is selected
215         * @since 10312
216         */
217        public final void setSelected(boolean selected) {
218            this.selected = selected;
219        }
220
221        /**
222         * Determines if this joined way is closed.
223         * @return {@code true} if this joined way is closed
224         */
225        public boolean isClosed() {
226            return nodes.isEmpty() || getLastNode().equals(getFirstNode());
227        }
228
229        /**
230         * Returns the first node.
231         * @return the first node
232         * @since 10312
233         */
234        public Node getFirstNode() {
235            return nodes.get(0);
236        }
237
238        /**
239         * Returns the last node.
240         * @return the last node
241         * @since 10312
242         */
243        public Node getLastNode() {
244            return nodes.get(nodes.size() - 1);
245        }
246    }
247
248    public static class PolyData extends JoinedWay {
249        public enum Intersection {
250            INSIDE,
251            OUTSIDE,
252            CROSSING
253        }
254
255        private final Path2D.Double poly;
256        private Rectangle2D bounds;
257        private final List<PolyData> inners;
258
259        /**
260         * Constructs a new {@code PolyData} from a closed way.
261         * @param closedWay closed way
262         */
263        public PolyData(Way closedWay) {
264            this(closedWay.getNodes(), closedWay.isSelected(), Collections.singleton(closedWay.getUniqueId()));
265        }
266
267        /**
268         * Constructs a new {@code PolyData} from a {@link JoinedWay}.
269         * @param joinedWay joined way
270         */
271        public PolyData(JoinedWay joinedWay) {
272            this(joinedWay.nodes, joinedWay.selected, joinedWay.wayIds);
273        }
274
275        private PolyData(List<Node> nodes, boolean selected, Collection<Long> wayIds) {
276            super(nodes, wayIds, selected);
277            this.inners = new ArrayList<>();
278            this.poly = new Path2D.Double();
279            this.poly.setWindingRule(Path2D.WIND_EVEN_ODD);
280            buildPoly();
281        }
282
283        /**
284         * Constructs a new {@code PolyData} from an existing {@code PolyData}.
285         * @param copy existing instance
286         */
287        public PolyData(PolyData copy) {
288            super(copy.nodes, copy.wayIds, copy.selected);
289            this.poly = (Path2D.Double) copy.poly.clone();
290            this.inners = new ArrayList<>(copy.inners);
291        }
292
293        private void buildPoly() {
294            boolean initial = true;
295            for (Node n : nodes) {
296                EastNorth p = n.getEastNorth();
297                if (p != null) {
298                    if (initial) {
299                        poly.moveTo(p.getX(), p.getY());
300                        initial = false;
301                    } else {
302                        poly.lineTo(p.getX(), p.getY());
303                    }
304                }
305            }
306            if (nodes.size() >= 3 && nodes.get(0) == nodes.get(nodes.size() - 1)) {
307                poly.closePath();
308            }
309            for (PolyData inner : inners) {
310                appendInner(inner.poly);
311            }
312        }
313
314        public Intersection contains(Path2D.Double p) {
315            int contains = 0;
316            int total = 0;
317            double[] coords = new double[6];
318            for (PathIterator it = p.getPathIterator(null); !it.isDone(); it.next()) {
319                switch (it.currentSegment(coords)) {
320                    case PathIterator.SEG_MOVETO:
321                    case PathIterator.SEG_LINETO:
322                        if (poly.contains(coords[0], coords[1])) {
323                            contains++;
324                        }
325                        total++;
326                        break;
327                    default: // Do nothing
328                }
329            }
330            if (contains == total) return Intersection.INSIDE;
331            if (contains == 0) return Intersection.OUTSIDE;
332            return Intersection.CROSSING;
333        }
334
335        public void addInner(PolyData inner) {
336            inners.add(inner);
337            appendInner(inner.poly);
338        }
339
340        private void appendInner(Path2D.Double inner) {
341            poly.append(inner.getPathIterator(null), false);
342        }
343
344        public Path2D.Double get() {
345            return poly;
346        }
347
348        public Rectangle2D getBounds() {
349            if (bounds == null) {
350                bounds = poly.getBounds2D();
351            }
352            return bounds;
353        }
354
355        public List<PolyData> getInners() {
356            return Collections.unmodifiableList(inners);
357        }
358
359        private void resetNodes(DataSet dataSet) {
360            if (!nodes.isEmpty()) {
361                DataSet ds = dataSet;
362                // Find DataSet (can be null for several nodes when undoing nodes creation, see #7162)
363                for (Iterator<Node> it = nodes.iterator(); it.hasNext() && ds == null;) {
364                    ds = it.next().getDataSet();
365                }
366                nodes.clear();
367                if (ds == null) {
368                    // DataSet still not found. This should not happen, but a warning does no harm
369                    Main.warn("DataSet not found while resetting nodes in Multipolygon. " +
370                            "This should not happen, you may report it to JOSM developers.");
371                } else if (wayIds.size() == 1) {
372                    Way w = (Way) ds.getPrimitiveById(wayIds.iterator().next(), OsmPrimitiveType.WAY);
373                    nodes.addAll(w.getNodes());
374                } else if (!wayIds.isEmpty()) {
375                    List<Way> waysToJoin = new ArrayList<>();
376                    for (Long wayId : wayIds) {
377                        Way w = (Way) ds.getPrimitiveById(wayId, OsmPrimitiveType.WAY);
378                        if (w != null && w.getNodesCount() > 0) { // fix #7173 (empty ways on purge)
379                            waysToJoin.add(w);
380                        }
381                    }
382                    if (!waysToJoin.isEmpty()) {
383                        nodes.addAll(joinWays(waysToJoin).iterator().next().getNodes());
384                    }
385                }
386                resetPoly();
387            }
388        }
389
390        private void resetPoly() {
391            poly.reset();
392            buildPoly();
393            bounds = null;
394        }
395
396        public void nodeMoved(NodeMovedEvent event) {
397            final Node n = event.getNode();
398            boolean innerChanged = false;
399            for (PolyData inner : inners) {
400                if (inner.nodes.contains(n)) {
401                    inner.resetPoly();
402                    innerChanged = true;
403                }
404            }
405            if (nodes.contains(n) || innerChanged) {
406                resetPoly();
407            }
408        }
409
410        public void wayNodesChanged(WayNodesChangedEvent event) {
411            final Long wayId = event.getChangedWay().getUniqueId();
412            boolean innerChanged = false;
413            for (PolyData inner : inners) {
414                if (inner.wayIds.contains(wayId)) {
415                    inner.resetNodes(event.getDataset());
416                    innerChanged = true;
417                }
418            }
419            if (wayIds.contains(wayId) || innerChanged) {
420                resetNodes(event.getDataset());
421            }
422        }
423
424        @Override
425        public boolean isClosed() {
426            if (nodes.size() < 3 || !getFirstNode().equals(getLastNode()))
427                return false;
428            for (PolyData inner : inners) {
429                if (!inner.isClosed())
430                    return false;
431            }
432            return true;
433        }
434
435        /**
436         * Calculate area and perimeter length in the given projection.
437         *
438         * @param projection the projection to use for the calculation, {@code null} defaults to {@link Main#getProjection()}
439         * @return area and perimeter
440         */
441        public AreaAndPerimeter getAreaAndPerimeter(Projection projection) {
442            AreaAndPerimeter ap = Geometry.getAreaAndPerimeter(nodes, projection);
443            double area = ap.getArea();
444            double perimeter = ap.getPerimeter();
445            for (PolyData inner : inners) {
446                AreaAndPerimeter apInner = inner.getAreaAndPerimeter(projection);
447                area -= apInner.getArea();
448                perimeter += apInner.getPerimeter();
449            }
450            return new AreaAndPerimeter(area, perimeter);
451        }
452    }
453
454    private final List<Way> innerWays = new ArrayList<>();
455    private final List<Way> outerWays = new ArrayList<>();
456    private final List<PolyData> combinedPolygons = new ArrayList<>();
457    private final List<Node> openEnds = new ArrayList<>();
458
459    private boolean incomplete;
460
461    /**
462     * Constructs a new {@code Multipolygon} from a relation.
463     * @param r relation
464     */
465    public Multipolygon(Relation r) {
466        load(r);
467    }
468
469    private void load(Relation r) {
470        MultipolygonRoleMatcher matcher = getMultipolygonRoleMatcher();
471
472        // Fill inner and outer list with valid ways
473        for (RelationMember m : r.getMembers()) {
474            if (m.getMember().isIncomplete()) {
475                this.incomplete = true;
476            } else if (m.getMember().isDrawable() && m.isWay()) {
477                Way w = m.getWay();
478
479                if (w.getNodesCount() < 2) {
480                    continue;
481                }
482
483                if (matcher.isInnerRole(m.getRole())) {
484                    innerWays.add(w);
485                } else if (!m.hasRole() || matcher.isOuterRole(m.getRole())) {
486                    outerWays.add(w);
487                } // Remaining roles ignored
488            } // Non ways ignored
489        }
490
491        final List<PolyData> innerPolygons = new ArrayList<>();
492        final List<PolyData> outerPolygons = new ArrayList<>();
493        createPolygons(innerWays, innerPolygons);
494        createPolygons(outerWays, outerPolygons);
495        if (!outerPolygons.isEmpty()) {
496            addInnerToOuters(innerPolygons, outerPolygons);
497        }
498    }
499
500    /**
501     * Determines if this multipolygon is incomplete.
502     * @return {@code true} if this multipolygon is incomplete
503     */
504    public final boolean isIncomplete() {
505        return incomplete;
506    }
507
508    private void createPolygons(List<Way> ways, List<PolyData> result) {
509        List<Way> waysToJoin = new ArrayList<>();
510        for (Way way: ways) {
511            if (way.isClosed()) {
512                result.add(new PolyData(way));
513            } else {
514                waysToJoin.add(way);
515            }
516        }
517
518        for (JoinedWay jw: joinWays(waysToJoin)) {
519            result.add(new PolyData(jw));
520            if (!jw.isClosed()) {
521                openEnds.add(jw.getFirstNode());
522                openEnds.add(jw.getLastNode());
523            }
524        }
525    }
526
527    public static Collection<JoinedWay> joinWays(Collection<Way> waysToJoin) {
528        final Collection<JoinedWay> result = new ArrayList<>();
529        final Way[] joinArray = waysToJoin.toArray(new Way[waysToJoin.size()]);
530        int left = waysToJoin.size();
531        while (left > 0) {
532            Way w = null;
533            boolean selected = false;
534            List<Node> nodes = null;
535            Set<Long> wayIds = new HashSet<>();
536            boolean joined = true;
537            while (joined && left > 0) {
538                joined = false;
539                for (int i = 0; i < joinArray.length && left != 0; ++i) {
540                    if (joinArray[i] != null) {
541                        Way c = joinArray[i];
542                        if (c.getNodesCount() == 0) {
543                            continue;
544                        }
545                        if (w == null) {
546                            w = c;
547                            selected = w.isSelected();
548                            joinArray[i] = null;
549                            --left;
550                        } else {
551                            int mode = 0;
552                            int cl = c.getNodesCount()-1;
553                            int nl;
554                            if (nodes == null) {
555                                nl = w.getNodesCount()-1;
556                                if (w.getNode(nl) == c.getNode(0)) {
557                                    mode = 21;
558                                } else if (w.getNode(nl) == c.getNode(cl)) {
559                                    mode = 22;
560                                } else if (w.getNode(0) == c.getNode(0)) {
561                                    mode = 11;
562                                } else if (w.getNode(0) == c.getNode(cl)) {
563                                    mode = 12;
564                                }
565                            } else {
566                                nl = nodes.size()-1;
567                                if (nodes.get(nl) == c.getNode(0)) {
568                                    mode = 21;
569                                } else if (nodes.get(0) == c.getNode(cl)) {
570                                    mode = 12;
571                                } else if (nodes.get(0) == c.getNode(0)) {
572                                    mode = 11;
573                                } else if (nodes.get(nl) == c.getNode(cl)) {
574                                    mode = 22;
575                                }
576                            }
577                            if (mode != 0) {
578                                joinArray[i] = null;
579                                joined = true;
580                                if (c.isSelected()) {
581                                    selected = true;
582                                }
583                                --left;
584                                if (nodes == null) {
585                                    nodes = w.getNodes();
586                                    wayIds.add(w.getUniqueId());
587                                }
588                                nodes.remove((mode == 21 || mode == 22) ? nl : 0);
589                                if (mode == 21) {
590                                    nodes.addAll(c.getNodes());
591                                } else if (mode == 12) {
592                                    nodes.addAll(0, c.getNodes());
593                                } else if (mode == 22) {
594                                    for (Node node : c.getNodes()) {
595                                        nodes.add(nl, node);
596                                    }
597                                } else /* mode == 11 */ {
598                                    for (Node node : c.getNodes()) {
599                                        nodes.add(0, node);
600                                    }
601                                }
602                                wayIds.add(c.getUniqueId());
603                            }
604                        }
605                    }
606                }
607            }
608
609            if (nodes == null && w != null) {
610                nodes = w.getNodes();
611                wayIds.add(w.getUniqueId());
612            }
613
614            if (nodes != null) {
615                result.add(new JoinedWay(nodes, wayIds, selected));
616            }
617        }
618
619        return result;
620    }
621
622    public PolyData findOuterPolygon(PolyData inner, List<PolyData> outerPolygons) {
623        // First try to test only bbox, use precise testing only if we don't get unique result
624        Rectangle2D innerBox = inner.getBounds();
625        PolyData insidePolygon = null;
626        PolyData intersectingPolygon = null;
627        int insideCount = 0;
628        int intersectingCount = 0;
629
630        for (PolyData outer: outerPolygons) {
631            if (outer.getBounds().contains(innerBox)) {
632                insidePolygon = outer;
633                insideCount++;
634            } else if (outer.getBounds().intersects(innerBox)) {
635                intersectingPolygon = outer;
636                intersectingCount++;
637            }
638        }
639
640        if (insideCount == 1)
641            return insidePolygon;
642        else if (intersectingCount == 1)
643            return intersectingPolygon;
644
645        PolyData result = null;
646        for (PolyData combined : outerPolygons) {
647            if (combined.contains(inner.poly) != Intersection.OUTSIDE
648                    && (result == null || result.contains(combined.poly) == Intersection.INSIDE)) {
649                result = combined;
650            }
651        }
652        return result;
653    }
654
655    private void addInnerToOuters(List<PolyData> innerPolygons, List<PolyData> outerPolygons) {
656        if (innerPolygons.isEmpty()) {
657            combinedPolygons.addAll(outerPolygons);
658        } else if (outerPolygons.size() == 1) {
659            PolyData combinedOuter = new PolyData(outerPolygons.get(0));
660            for (PolyData inner: innerPolygons) {
661                combinedOuter.addInner(inner);
662            }
663            combinedPolygons.add(combinedOuter);
664        } else {
665            for (PolyData outer: outerPolygons) {
666                combinedPolygons.add(new PolyData(outer));
667            }
668
669            for (PolyData pdInner: innerPolygons) {
670                PolyData o = findOuterPolygon(pdInner, combinedPolygons);
671                if (o == null) {
672                    o = outerPolygons.get(0);
673                }
674                o.addInner(pdInner);
675            }
676        }
677    }
678
679    /**
680     * Replies the list of outer ways.
681     * @return the list of outer ways
682     */
683    public List<Way> getOuterWays() {
684        return Collections.unmodifiableList(outerWays);
685    }
686
687    /**
688     * Replies the list of inner ways.
689     * @return the list of inner ways
690     */
691    public List<Way> getInnerWays() {
692        return Collections.unmodifiableList(innerWays);
693    }
694
695    /**
696     * Replies the list of combined polygons.
697     * @return the list of combined polygons
698     */
699    public List<PolyData> getCombinedPolygons() {
700        return Collections.unmodifiableList(combinedPolygons);
701    }
702
703    /**
704     * Replies the list of inner polygons.
705     * @return the list of inner polygons
706     */
707    public List<PolyData> getInnerPolygons() {
708        final List<PolyData> innerPolygons = new ArrayList<>();
709        createPolygons(innerWays, innerPolygons);
710        return innerPolygons;
711    }
712
713    /**
714     * Replies the list of outer polygons.
715     * @return the list of outer polygons
716     */
717    public List<PolyData> getOuterPolygons() {
718        final List<PolyData> outerPolygons = new ArrayList<>();
719        createPolygons(outerWays, outerPolygons);
720        return outerPolygons;
721    }
722
723    /**
724     * Returns the start and end node of non-closed rings.
725     * @return the start and end node of non-closed rings.
726     */
727    public List<Node> getOpenEnds() {
728        return Collections.unmodifiableList(openEnds);
729    }
730}