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