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