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 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    private static MultipolygonRoleMatcher getMultipolygonRoleMatcher() {
152        if (roleMatcher == null) {
153            roleMatcher = new MultipolygonRoleMatcher();
154            if (Main.pref != null){
155                roleMatcher.initFromPreferences();
156                Main.pref.addPreferenceChangeListener(roleMatcher);
157            }
158        }
159        return roleMatcher;
160    }
161
162    public static class JoinedWay {
163        private final List<Node> nodes;
164        private final Collection<Long> wayIds;
165        private final boolean selected;
166
167        public JoinedWay(List<Node> nodes, Collection<Long> wayIds, boolean selected) {
168            this.nodes = nodes;
169            this.wayIds = wayIds;
170            this.selected = selected;
171        }
172
173        public List<Node> getNodes() {
174            return nodes;
175        }
176
177        public Collection<Long> getWayIds() {
178            return wayIds;
179        }
180
181        public boolean isSelected() {
182            return selected;
183        }
184
185        public boolean isClosed() {
186            return nodes.isEmpty() || nodes.get(nodes.size() - 1).equals(nodes.get(0));
187        }
188    }
189
190    public static class PolyData {
191        public enum Intersection {INSIDE, OUTSIDE, CROSSING}
192
193        private final Path2D.Double poly;
194        public boolean selected;
195        private Rectangle2D bounds;
196        private final Collection<Long> wayIds;
197        private final List<Node> nodes;
198        private final List<PolyData> inners;
199
200        public PolyData(Way closedWay) {
201            this(closedWay.getNodes(), closedWay.isSelected(), Collections.singleton(closedWay.getUniqueId()));
202        }
203
204        public PolyData(JoinedWay joinedWay) {
205            this(joinedWay.getNodes(), joinedWay.isSelected(), joinedWay.getWayIds());
206        }
207
208        private PolyData(List<Node> nodes, boolean selected, Collection<Long> wayIds) {
209            this.wayIds = Collections.unmodifiableCollection(wayIds);
210            this.nodes = new ArrayList<>(nodes);
211            this.selected = selected;
212            this.inners = new ArrayList<>();
213            this.poly = new Path2D.Double();
214            this.poly.setWindingRule(Path2D.WIND_EVEN_ODD);
215            buildPoly();
216        }
217
218        private void buildPoly() {
219            boolean initial = true;
220            for (Node n : nodes) {
221                EastNorth p = n.getEastNorth();
222                if (p != null) {
223                    if (initial) {
224                        poly.moveTo(p.getX(), p.getY());
225                        initial = false;
226                    } else {
227                        poly.lineTo(p.getX(), p.getY());
228                    }
229                }
230            }
231            if (!initial) { // fix #7593
232                poly.closePath();
233            }
234            for (PolyData inner : inners) {
235                appendInner(inner.poly);
236            }
237        }
238
239        public PolyData(PolyData copy) {
240            this.selected = copy.selected;
241            this.poly = (Double) copy.poly.clone();
242            this.wayIds = Collections.unmodifiableCollection(copy.wayIds);
243            this.nodes = new ArrayList<>(copy.nodes);
244            this.inners = new ArrayList<>(copy.inners);
245        }
246
247        public Intersection contains(Path2D.Double p) {
248            int contains = 0;
249            int total = 0;
250            double[] coords = new double[6];
251            for (PathIterator it = p.getPathIterator(null); !it.isDone(); it.next()) {
252                switch (it.currentSegment(coords)) {
253                    case PathIterator.SEG_MOVETO:
254                    case PathIterator.SEG_LINETO:
255                        if (poly.contains(coords[0], coords[1])) {
256                            contains++;
257                        }
258                        total++;
259                }
260            }
261            if (contains == total) return Intersection.INSIDE;
262            if (contains == 0) return Intersection.OUTSIDE;
263            return Intersection.CROSSING;
264        }
265
266        public void addInner(PolyData inner) {
267            inners.add(inner);
268            appendInner(inner.poly);
269        }
270
271        private void appendInner(Path2D.Double inner) {
272            poly.append(inner.getPathIterator(null), false);
273        }
274
275        public Path2D.Double get() {
276            return poly;
277        }
278
279        public Rectangle2D getBounds() {
280            if (bounds == null) {
281                bounds = poly.getBounds2D();
282            }
283            return bounds;
284        }
285
286        public Collection<Long> getWayIds() {
287            return wayIds;
288        }
289
290        private void resetNodes(DataSet dataSet) {
291            if (!nodes.isEmpty()) {
292                DataSet ds = dataSet;
293                // Find DataSet (can be null for several nodes when undoing nodes creation, see #7162)
294                for (Iterator<Node> it = nodes.iterator(); it.hasNext() && ds == null; ) {
295                    ds = it.next().getDataSet();
296                }
297                nodes.clear();
298                if (ds == null) {
299                    // DataSet still not found. This should not happen, but a warning does no harm
300                    Main.warn("DataSet not found while resetting nodes in Multipolygon. This should not happen, you may report it to JOSM developers.");
301                } else if (wayIds.size() == 1) {
302                    Way w = (Way) ds.getPrimitiveById(wayIds.iterator().next(), OsmPrimitiveType.WAY);
303                    nodes.addAll(w.getNodes());
304                } else if (!wayIds.isEmpty()) {
305                    List<Way> waysToJoin = new ArrayList<>();
306                    for (Long wayId : wayIds) {
307                        Way w = (Way) ds.getPrimitiveById(wayId, OsmPrimitiveType.WAY);
308                        if (w != null && w.getNodesCount() > 0) { // fix #7173 (empty ways on purge)
309                            waysToJoin.add(w);
310                        }
311                    }
312                    if (!waysToJoin.isEmpty()) {
313                        nodes.addAll(joinWays(waysToJoin).iterator().next().getNodes());
314                    }
315                }
316                resetPoly();
317            }
318        }
319
320        private void resetPoly() {
321            poly.reset();
322            buildPoly();
323            bounds = null;
324        }
325
326        public void nodeMoved(NodeMovedEvent event) {
327            final Node n = event.getNode();
328            boolean innerChanged = false;
329            for (PolyData inner : inners) {
330                if (inner.nodes.contains(n)) {
331                    inner.resetPoly();
332                    innerChanged = true;
333                }
334            }
335            if (nodes.contains(n) || innerChanged) {
336                resetPoly();
337            }
338        }
339
340        public void wayNodesChanged(WayNodesChangedEvent event) {
341            final Long wayId = event.getChangedWay().getUniqueId();
342            boolean innerChanged = false;
343            for (PolyData inner : inners) {
344                if (inner.wayIds.contains(wayId)) {
345                    inner.resetNodes(event.getDataset());
346                    innerChanged = true;
347                }
348            }
349            if (wayIds.contains(wayId) || innerChanged) {
350                resetNodes(event.getDataset());
351            }
352        }
353    }
354
355    private final List<Way> innerWays = new ArrayList<>();
356    private final List<Way> outerWays = new ArrayList<>();
357    private final List<PolyData> innerPolygons = new ArrayList<>();
358    private final List<PolyData> outerPolygons = new ArrayList<>();
359    private final List<PolyData> combinedPolygons = new ArrayList<>();
360
361    private boolean incomplete;
362
363    public Multipolygon(Relation r) {
364        load(r);
365    }
366
367    private final void load(Relation r) {
368        MultipolygonRoleMatcher matcher = getMultipolygonRoleMatcher();
369
370        // Fill inner and outer list with valid ways
371        for (RelationMember m : r.getMembers()) {
372            if (m.getMember().isIncomplete()) {
373                this.incomplete = true;
374            } else if (m.getMember().isDrawable()) {
375                if (m.isWay()) {
376                    Way w = m.getWay();
377
378                    if (w.getNodesCount() < 2) {
379                        continue;
380                    }
381
382                    if (matcher.isInnerRole(m.getRole())) {
383                        innerWays.add(w);
384                    } else if (matcher.isOuterRole(m.getRole())) {
385                        outerWays.add(w);
386                    } else if (!m.hasRole()) {
387                        outerWays.add(w);
388                    } // Remaining roles ignored
389                } // Non ways ignored
390            }
391        }
392
393        createPolygons(innerWays, innerPolygons);
394        createPolygons(outerWays, outerPolygons);
395        if (!outerPolygons.isEmpty()) {
396            addInnerToOuters();
397        }
398    }
399
400    public final boolean isIncomplete() {
401        return incomplete;
402    }
403
404    private void createPolygons(List<Way> ways, List<PolyData> result) {
405        List<Way> waysToJoin = new ArrayList<>();
406        for (Way way: ways) {
407            if (way.isClosed()) {
408                result.add(new PolyData(way));
409            } else {
410                waysToJoin.add(way);
411            }
412        }
413
414        for (JoinedWay jw: joinWays(waysToJoin)) {
415            result.add(new PolyData(jw));
416        }
417    }
418
419    public static Collection<JoinedWay> joinWays(Collection<Way> waysToJoin) {
420        final Collection<JoinedWay> result = new ArrayList<>();
421        final Way[] joinArray = waysToJoin.toArray(new Way[waysToJoin.size()]);
422        int left = waysToJoin.size();
423        while (left > 0) {
424            Way w = null;
425            boolean selected = false;
426            List<Node> nodes = null;
427            Set<Long> wayIds = new HashSet<>();
428            boolean joined = true;
429            while (joined && left > 0) {
430                joined = false;
431                for (int i = 0; i < joinArray.length && left != 0; ++i) {
432                    if (joinArray[i] != null) {
433                        Way c = joinArray[i];
434                        if (c.getNodesCount() == 0) {
435                            continue;
436                        }
437                        if (w == null) {
438                            w = c;
439                            selected = w.isSelected();
440                            joinArray[i] = null;
441                            --left;
442                        } else {
443                            int mode = 0;
444                            int cl = c.getNodesCount()-1;
445                            int nl;
446                            if (nodes == null) {
447                                nl = w.getNodesCount()-1;
448                                if (w.getNode(nl) == c.getNode(0)) {
449                                    mode = 21;
450                                } else if (w.getNode(nl) == c.getNode(cl)) {
451                                    mode = 22;
452                                } else if (w.getNode(0) == c.getNode(0)) {
453                                    mode = 11;
454                                } else if (w.getNode(0) == c.getNode(cl)) {
455                                    mode = 12;
456                                }
457                            } else {
458                                nl = nodes.size()-1;
459                                if (nodes.get(nl) == c.getNode(0)) {
460                                    mode = 21;
461                                } else if (nodes.get(0) == c.getNode(cl)) {
462                                    mode = 12;
463                                } else if (nodes.get(0) == c.getNode(0)) {
464                                    mode = 11;
465                                } else if (nodes.get(nl) == c.getNode(cl)) {
466                                    mode = 22;
467                                }
468                            }
469                            if (mode != 0) {
470                                joinArray[i] = null;
471                                joined = true;
472                                if (c.isSelected()) {
473                                    selected = true;
474                                }
475                                --left;
476                                if (nodes == null) {
477                                    nodes = w.getNodes();
478                                    wayIds.add(w.getUniqueId());
479                                }
480                                nodes.remove((mode == 21 || mode == 22) ? nl : 0);
481                                if (mode == 21) {
482                                    nodes.addAll(c.getNodes());
483                                } else if (mode == 12) {
484                                    nodes.addAll(0, c.getNodes());
485                                } else if (mode == 22) {
486                                    for (Node node : c.getNodes()) {
487                                        nodes.add(nl, node);
488                                    }
489                                } else /* mode == 11 */ {
490                                    for (Node node : c.getNodes()) {
491                                        nodes.add(0, node);
492                                    }
493                                }
494                                wayIds.add(c.getUniqueId());
495                            }
496                        }
497                    }
498                }
499            }
500
501            if (nodes == null && w != null) {
502                nodes = w.getNodes();
503                wayIds.add(w.getUniqueId());
504            }
505
506            result.add(new JoinedWay(nodes, wayIds, selected));
507        }
508
509        return result;
510    }
511
512    public PolyData findOuterPolygon(PolyData inner, List<PolyData> outerPolygons) {
513
514        // First try to test only bbox, use precise testing only if we don't get unique result
515        Rectangle2D innerBox = inner.getBounds();
516        PolyData insidePolygon = null;
517        PolyData intersectingPolygon = null;
518        int insideCount = 0;
519        int intersectingCount = 0;
520
521        for (PolyData outer: outerPolygons) {
522            if (outer.getBounds().contains(innerBox)) {
523                insidePolygon = outer;
524                insideCount++;
525            } else if (outer.getBounds().intersects(innerBox)) {
526                intersectingPolygon = outer;
527                intersectingCount++;
528            }
529        }
530
531        if (insideCount == 1)
532            return insidePolygon;
533        else if (intersectingCount == 1)
534            return intersectingPolygon;
535
536        PolyData result = null;
537        for (PolyData combined : outerPolygons) {
538            if (combined.contains(inner.poly) != Intersection.OUTSIDE) {
539                if (result == null || result.contains(combined.poly) == Intersection.INSIDE) {
540                    result = combined;
541                }
542            }
543        }
544        return result;
545    }
546
547    private final void addInnerToOuters()  {
548
549        if (innerPolygons.isEmpty()) {
550            combinedPolygons.addAll(outerPolygons);
551        } else if (outerPolygons.size() == 1) {
552            PolyData combinedOuter = new PolyData(outerPolygons.get(0));
553            for (PolyData inner: innerPolygons) {
554                combinedOuter.addInner(inner);
555            }
556            combinedPolygons.add(combinedOuter);
557        } else {
558            for (PolyData outer: outerPolygons) {
559                combinedPolygons.add(new PolyData(outer));
560            }
561
562            for (PolyData pdInner: innerPolygons) {
563                PolyData o = findOuterPolygon(pdInner, combinedPolygons);
564                if (o == null) {
565                    o = outerPolygons.get(0);
566                }
567                o.addInner(pdInner);
568            }
569        }
570
571        // Clear inner and outer polygons to reduce memory footprint
572        innerPolygons.clear();
573        outerPolygons.clear();
574    }
575
576    /**
577     * Replies the list of outer ways.
578     * @return the list of outer ways
579     */
580    public List<Way> getOuterWays() {
581        return outerWays;
582    }
583
584    /**
585     * Replies the list of inner ways.
586     * @return the list of inner ways
587     */
588    public List<Way> getInnerWays() {
589        return innerWays;
590    }
591
592    public List<PolyData> getCombinedPolygons() {
593        return combinedPolygons;
594    }
595}