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    public static class JoinedWay {
166        protected final List<Node> nodes;
167        protected final Collection<Long> wayIds;
168        protected boolean selected;
169
170        /**
171         * Constructs a new {@code JoinedWay}.
172         * @param nodes list of nodes
173         * @param wayIds list of way IDs
174         * @param selected whether joined way is selected or not
175         */
176        public JoinedWay(List<Node> nodes, Collection<Long> wayIds, boolean selected) {
177            this.nodes = new ArrayList<>(nodes);
178            this.wayIds = new ArrayList<>(wayIds);
179            this.selected = selected;
180        }
181
182        /**
183         * Replies the list of nodes.
184         * @return the list of nodes
185         */
186        public List<Node> getNodes() {
187            return Collections.unmodifiableList(nodes);
188        }
189
190        /**
191         * Replies the list of way IDs.
192         * @return the list of way IDs
193         */
194        public Collection<Long> getWayIds() {
195            return Collections.unmodifiableCollection(wayIds);
196        }
197
198        /**
199         * Determines if this is selected.
200         * @return {@code true} if this is selected
201         */
202        public final boolean isSelected() {
203            return selected;
204        }
205
206        /**
207         * Sets whether this is selected
208         * @param selected {@code true} if this is selected
209         * @since 10312
210         */
211        public final void setSelected(boolean selected) {
212            this.selected = selected;
213        }
214
215        /**
216         * Determines if this joined way is closed.
217         * @return {@code true} if this joined way is closed
218         */
219        public boolean isClosed() {
220            return nodes.isEmpty() || getLastNode().equals(getFirstNode());
221        }
222
223        /**
224         * Returns the first node.
225         * @return the first node
226         * @since 10312
227         */
228        public Node getFirstNode() {
229            return nodes.get(0);
230        }
231
232        /**
233         * Returns the last node.
234         * @return the last node
235         * @since 10312
236         */
237        public Node getLastNode() {
238            return nodes.get(nodes.size() - 1);
239        }
240    }
241
242    public static class PolyData extends JoinedWay {
243        public enum Intersection {
244            INSIDE,
245            OUTSIDE,
246            CROSSING
247        }
248
249        private final Path2D.Double poly;
250        private Rectangle2D bounds;
251        private final List<PolyData> inners;
252
253        /**
254         * Constructs a new {@code PolyData} from a closed way.
255         * @param closedWay closed way
256         */
257        public PolyData(Way closedWay) {
258            this(closedWay.getNodes(), closedWay.isSelected(), Collections.singleton(closedWay.getUniqueId()));
259        }
260
261        /**
262         * Constructs a new {@code PolyData} from a {@link JoinedWay}.
263         * @param joinedWay joined way
264         */
265        public PolyData(JoinedWay joinedWay) {
266            this(joinedWay.nodes, joinedWay.selected, joinedWay.wayIds);
267        }
268
269        private PolyData(List<Node> nodes, boolean selected, Collection<Long> wayIds) {
270            super(nodes, wayIds, selected);
271            this.inners = new ArrayList<>();
272            this.poly = new Path2D.Double();
273            this.poly.setWindingRule(Path2D.WIND_EVEN_ODD);
274            buildPoly();
275        }
276
277        /**
278         * Constructs a new {@code PolyData} from an existing {@code PolyData}.
279         * @param copy existing instance
280         */
281        public PolyData(PolyData copy) {
282            super(copy.nodes, copy.wayIds, copy.selected);
283            this.poly = (Path2D.Double) copy.poly.clone();
284            this.inners = new ArrayList<>(copy.inners);
285        }
286
287        private void buildPoly() {
288            boolean initial = true;
289            for (Node n : nodes) {
290                EastNorth p = n.getEastNorth();
291                if (p != null) {
292                    if (initial) {
293                        poly.moveTo(p.getX(), p.getY());
294                        initial = false;
295                    } else {
296                        poly.lineTo(p.getX(), p.getY());
297                    }
298                }
299            }
300            if (nodes.size() >= 3 && nodes.get(0) == nodes.get(nodes.size() - 1)) {
301                poly.closePath();
302            }
303            for (PolyData inner : inners) {
304                appendInner(inner.poly);
305            }
306        }
307
308        public Intersection contains(Path2D.Double p) {
309            int contains = 0;
310            int total = 0;
311            double[] coords = new double[6];
312            for (PathIterator it = p.getPathIterator(null); !it.isDone(); it.next()) {
313                switch (it.currentSegment(coords)) {
314                    case PathIterator.SEG_MOVETO:
315                    case PathIterator.SEG_LINETO:
316                        if (poly.contains(coords[0], coords[1])) {
317                            contains++;
318                        }
319                        total++;
320                        break;
321                    default: // Do nothing
322                }
323            }
324            if (contains == total) return Intersection.INSIDE;
325            if (contains == 0) return Intersection.OUTSIDE;
326            return Intersection.CROSSING;
327        }
328
329        public void addInner(PolyData inner) {
330            inners.add(inner);
331            appendInner(inner.poly);
332        }
333
334        private void appendInner(Path2D.Double inner) {
335            poly.append(inner.getPathIterator(null), false);
336        }
337
338        public Path2D.Double get() {
339            return poly;
340        }
341
342        public Rectangle2D getBounds() {
343            if (bounds == null) {
344                bounds = poly.getBounds2D();
345            }
346            return bounds;
347        }
348
349        public List<PolyData> getInners() {
350            return Collections.unmodifiableList(inners);
351        }
352
353        private void resetNodes(DataSet dataSet) {
354            if (!nodes.isEmpty()) {
355                DataSet ds = dataSet;
356                // Find DataSet (can be null for several nodes when undoing nodes creation, see #7162)
357                for (Iterator<Node> it = nodes.iterator(); it.hasNext() && ds == null;) {
358                    ds = it.next().getDataSet();
359                }
360                nodes.clear();
361                if (ds == null) {
362                    // DataSet still not found. This should not happen, but a warning does no harm
363                    Main.warn("DataSet not found while resetting nodes in Multipolygon. " +
364                            "This should not happen, you may report it to JOSM developers.");
365                } else if (wayIds.size() == 1) {
366                    Way w = (Way) ds.getPrimitiveById(wayIds.iterator().next(), OsmPrimitiveType.WAY);
367                    nodes.addAll(w.getNodes());
368                } else if (!wayIds.isEmpty()) {
369                    List<Way> waysToJoin = new ArrayList<>();
370                    for (Long wayId : wayIds) {
371                        Way w = (Way) ds.getPrimitiveById(wayId, OsmPrimitiveType.WAY);
372                        if (w != null && w.getNodesCount() > 0) { // fix #7173 (empty ways on purge)
373                            waysToJoin.add(w);
374                        }
375                    }
376                    if (!waysToJoin.isEmpty()) {
377                        nodes.addAll(joinWays(waysToJoin).iterator().next().getNodes());
378                    }
379                }
380                resetPoly();
381            }
382        }
383
384        private void resetPoly() {
385            poly.reset();
386            buildPoly();
387            bounds = null;
388        }
389
390        public void nodeMoved(NodeMovedEvent event) {
391            final Node n = event.getNode();
392            boolean innerChanged = false;
393            for (PolyData inner : inners) {
394                if (inner.nodes.contains(n)) {
395                    inner.resetPoly();
396                    innerChanged = true;
397                }
398            }
399            if (nodes.contains(n) || innerChanged) {
400                resetPoly();
401            }
402        }
403
404        public void wayNodesChanged(WayNodesChangedEvent event) {
405            final Long wayId = event.getChangedWay().getUniqueId();
406            boolean innerChanged = false;
407            for (PolyData inner : inners) {
408                if (inner.wayIds.contains(wayId)) {
409                    inner.resetNodes(event.getDataset());
410                    innerChanged = true;
411                }
412            }
413            if (wayIds.contains(wayId) || innerChanged) {
414                resetNodes(event.getDataset());
415            }
416        }
417
418        @Override
419        public boolean isClosed() {
420            if (nodes.size() < 3 || !getFirstNode().equals(getLastNode()))
421                return false;
422            for (PolyData inner : inners) {
423                if (!inner.isClosed())
424                    return false;
425            }
426            return true;
427        }
428
429        /**
430         * Calculate area and perimeter length in the given projection.
431         *
432         * @param projection the projection to use for the calculation, {@code null} defaults to {@link Main#getProjection()}
433         * @return area and perimeter
434         */
435        public AreaAndPerimeter getAreaAndPerimeter(Projection projection) {
436            AreaAndPerimeter ap = Geometry.getAreaAndPerimeter(nodes, projection);
437            double area = ap.getArea();
438            double perimeter = ap.getPerimeter();
439            for (PolyData inner : inners) {
440                AreaAndPerimeter apInner = inner.getAreaAndPerimeter(projection);
441                area -= apInner.getArea();
442                perimeter += apInner.getPerimeter();
443            }
444            return new AreaAndPerimeter(area, perimeter);
445        }
446    }
447
448    private final List<Way> innerWays = new ArrayList<>();
449    private final List<Way> outerWays = new ArrayList<>();
450    private final List<PolyData> combinedPolygons = new ArrayList<>();
451    private final List<Node> openEnds = new ArrayList<>();
452
453    private boolean incomplete;
454
455    /**
456     * Constructs a new {@code Multipolygon} from a relation.
457     * @param r relation
458     */
459    public Multipolygon(Relation r) {
460        load(r);
461    }
462
463    private void load(Relation r) {
464        MultipolygonRoleMatcher matcher = getMultipolygonRoleMatcher();
465
466        // Fill inner and outer list with valid ways
467        for (RelationMember m : r.getMembers()) {
468            if (m.getMember().isIncomplete()) {
469                this.incomplete = true;
470            } else if (m.getMember().isDrawable() && m.isWay()) {
471                Way w = m.getWay();
472
473                if (w.getNodesCount() < 2) {
474                    continue;
475                }
476
477                if (matcher.isInnerRole(m.getRole())) {
478                    innerWays.add(w);
479                } else if (!m.hasRole() || matcher.isOuterRole(m.getRole())) {
480                    outerWays.add(w);
481                } // Remaining roles ignored
482            } // Non ways ignored
483        }
484
485        final List<PolyData> innerPolygons = new ArrayList<>();
486        final List<PolyData> outerPolygons = new ArrayList<>();
487        createPolygons(innerWays, innerPolygons);
488        createPolygons(outerWays, outerPolygons);
489        if (!outerPolygons.isEmpty()) {
490            addInnerToOuters(innerPolygons, outerPolygons);
491        }
492    }
493
494    /**
495     * Determines if this multipolygon is incomplete.
496     * @return {@code true} if this multipolygon is incomplete
497     */
498    public final boolean isIncomplete() {
499        return incomplete;
500    }
501
502    private void createPolygons(List<Way> ways, List<PolyData> result) {
503        List<Way> waysToJoin = new ArrayList<>();
504        for (Way way: ways) {
505            if (way.isClosed()) {
506                result.add(new PolyData(way));
507            } else {
508                waysToJoin.add(way);
509            }
510        }
511
512        for (JoinedWay jw: joinWays(waysToJoin)) {
513            result.add(new PolyData(jw));
514            if (!jw.isClosed()) {
515                openEnds.add(jw.getFirstNode());
516                openEnds.add(jw.getLastNode());
517            }
518        }
519    }
520
521    public static Collection<JoinedWay> joinWays(Collection<Way> waysToJoin) {
522        final Collection<JoinedWay> result = new ArrayList<>();
523        final Way[] joinArray = waysToJoin.toArray(new Way[waysToJoin.size()]);
524        int left = waysToJoin.size();
525        while (left > 0) {
526            Way w = null;
527            boolean selected = false;
528            List<Node> nodes = null;
529            Set<Long> wayIds = new HashSet<>();
530            boolean joined = true;
531            while (joined && left > 0) {
532                joined = false;
533                for (int i = 0; i < joinArray.length && left != 0; ++i) {
534                    if (joinArray[i] != null) {
535                        Way c = joinArray[i];
536                        if (c.getNodesCount() == 0) {
537                            continue;
538                        }
539                        if (w == null) {
540                            w = c;
541                            selected = w.isSelected();
542                            joinArray[i] = null;
543                            --left;
544                        } else {
545                            int mode = 0;
546                            int cl = c.getNodesCount()-1;
547                            int nl;
548                            if (nodes == null) {
549                                nl = w.getNodesCount()-1;
550                                if (w.getNode(nl) == c.getNode(0)) {
551                                    mode = 21;
552                                } else if (w.getNode(nl) == c.getNode(cl)) {
553                                    mode = 22;
554                                } else if (w.getNode(0) == c.getNode(0)) {
555                                    mode = 11;
556                                } else if (w.getNode(0) == c.getNode(cl)) {
557                                    mode = 12;
558                                }
559                            } else {
560                                nl = nodes.size()-1;
561                                if (nodes.get(nl) == c.getNode(0)) {
562                                    mode = 21;
563                                } else if (nodes.get(0) == c.getNode(cl)) {
564                                    mode = 12;
565                                } else if (nodes.get(0) == c.getNode(0)) {
566                                    mode = 11;
567                                } else if (nodes.get(nl) == c.getNode(cl)) {
568                                    mode = 22;
569                                }
570                            }
571                            if (mode != 0) {
572                                joinArray[i] = null;
573                                joined = true;
574                                if (c.isSelected()) {
575                                    selected = true;
576                                }
577                                --left;
578                                if (nodes == null) {
579                                    nodes = w.getNodes();
580                                    wayIds.add(w.getUniqueId());
581                                }
582                                nodes.remove((mode == 21 || mode == 22) ? nl : 0);
583                                if (mode == 21) {
584                                    nodes.addAll(c.getNodes());
585                                } else if (mode == 12) {
586                                    nodes.addAll(0, c.getNodes());
587                                } else if (mode == 22) {
588                                    for (Node node : c.getNodes()) {
589                                        nodes.add(nl, node);
590                                    }
591                                } else /* mode == 11 */ {
592                                    for (Node node : c.getNodes()) {
593                                        nodes.add(0, node);
594                                    }
595                                }
596                                wayIds.add(c.getUniqueId());
597                            }
598                        }
599                    }
600                }
601            }
602
603            if (nodes == null && w != null) {
604                nodes = w.getNodes();
605                wayIds.add(w.getUniqueId());
606            }
607
608            result.add(new JoinedWay(nodes, wayIds, selected));
609        }
610
611        return result;
612    }
613
614    public PolyData findOuterPolygon(PolyData inner, List<PolyData> outerPolygons) {
615        // First try to test only bbox, use precise testing only if we don't get unique result
616        Rectangle2D innerBox = inner.getBounds();
617        PolyData insidePolygon = null;
618        PolyData intersectingPolygon = null;
619        int insideCount = 0;
620        int intersectingCount = 0;
621
622        for (PolyData outer: outerPolygons) {
623            if (outer.getBounds().contains(innerBox)) {
624                insidePolygon = outer;
625                insideCount++;
626            } else if (outer.getBounds().intersects(innerBox)) {
627                intersectingPolygon = outer;
628                intersectingCount++;
629            }
630        }
631
632        if (insideCount == 1)
633            return insidePolygon;
634        else if (intersectingCount == 1)
635            return intersectingPolygon;
636
637        PolyData result = null;
638        for (PolyData combined : outerPolygons) {
639            if (combined.contains(inner.poly) != Intersection.OUTSIDE) {
640                if (result == null || result.contains(combined.poly) == Intersection.INSIDE) {
641                    result = combined;
642                }
643            }
644        }
645        return result;
646    }
647
648    private void addInnerToOuters(List<PolyData> innerPolygons, List<PolyData> outerPolygons) {
649        if (innerPolygons.isEmpty()) {
650            combinedPolygons.addAll(outerPolygons);
651        } else if (outerPolygons.size() == 1) {
652            PolyData combinedOuter = new PolyData(outerPolygons.get(0));
653            for (PolyData inner: innerPolygons) {
654                combinedOuter.addInner(inner);
655            }
656            combinedPolygons.add(combinedOuter);
657        } else {
658            for (PolyData outer: outerPolygons) {
659                combinedPolygons.add(new PolyData(outer));
660            }
661
662            for (PolyData pdInner: innerPolygons) {
663                PolyData o = findOuterPolygon(pdInner, combinedPolygons);
664                if (o == null) {
665                    o = outerPolygons.get(0);
666                }
667                o.addInner(pdInner);
668            }
669        }
670    }
671
672    /**
673     * Replies the list of outer ways.
674     * @return the list of outer ways
675     */
676    public List<Way> getOuterWays() {
677        return Collections.unmodifiableList(outerWays);
678    }
679
680    /**
681     * Replies the list of inner ways.
682     * @return the list of inner ways
683     */
684    public List<Way> getInnerWays() {
685        return Collections.unmodifiableList(innerWays);
686    }
687
688    /**
689     * Replies the list of combined polygons.
690     * @return the list of combined polygons
691     */
692    public List<PolyData> getCombinedPolygons() {
693        return Collections.unmodifiableList(combinedPolygons);
694    }
695
696    /**
697     * Replies the list of inner polygons.
698     * @return the list of inner polygons
699     */
700    public List<PolyData> getInnerPolygons() {
701        final List<PolyData> innerPolygons = new ArrayList<>();
702        createPolygons(innerWays, innerPolygons);
703        return innerPolygons;
704    }
705
706    /**
707     * Replies the list of outer polygons.
708     * @return the list of outer polygons
709     */
710    public List<PolyData> getOuterPolygons() {
711        final List<PolyData> outerPolygons = new ArrayList<>();
712        createPolygons(outerWays, outerPolygons);
713        return outerPolygons;
714    }
715
716    /**
717     * Returns the start and end node of non-closed rings.
718     * @return the start and end node of non-closed rings.
719     */
720    public List<Node> getOpenEnds() {
721        return Collections.unmodifiableList(openEnds);
722    }
723}