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