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