001    // License: GPL. For details, see LICENSE file.
002    package org.openstreetmap.josm.data.osm.visitor.paint.relations;
003    
004    import java.awt.geom.Path2D;
005    import java.awt.geom.Path2D.Double;
006    import java.awt.geom.PathIterator;
007    import java.awt.geom.Point2D;
008    import java.awt.geom.Rectangle2D;
009    import java.util.ArrayList;
010    import java.util.Collection;
011    import java.util.Collections;
012    import java.util.HashSet;
013    import java.util.Iterator;
014    import java.util.List;
015    import java.util.Set;
016    
017    import org.openstreetmap.josm.Main;
018    import org.openstreetmap.josm.data.Preferences.PreferenceChangeEvent;
019    import org.openstreetmap.josm.data.Preferences.PreferenceChangedListener;
020    import org.openstreetmap.josm.data.osm.DataSet;
021    import org.openstreetmap.josm.data.osm.Node;
022    import org.openstreetmap.josm.data.osm.OsmPrimitiveType;
023    import org.openstreetmap.josm.data.osm.Relation;
024    import org.openstreetmap.josm.data.osm.RelationMember;
025    import org.openstreetmap.josm.data.osm.Way;
026    import org.openstreetmap.josm.data.osm.event.NodeMovedEvent;
027    import org.openstreetmap.josm.data.osm.event.WayNodesChangedEvent;
028    import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.PolyData.Intersection;
029    
030    public 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        static public 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        static public 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        static public 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        static public 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<String>();
059            private final List<String> outerRolePrefixes = new ArrayList<String>();
060            private final List<String> innerExactRoles = new ArrayList<String>();
061            private final List<String> innerRolePrefixes = new ArrayList<String>();
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<Node>(nodes);
205                this.selected = selected;
206                this.inners = new ArrayList<Multipolygon.PolyData>();
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                    Point2D 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<Node>(copy.nodes);
238                this.inners = new ArrayList<Multipolygon.PolyData>(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                        System.err.println("Warning: 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 {
299                        List<Way> waysToJoin = new ArrayList<Way>();
300                        for (Iterator<Long> it = wayIds.iterator(); it.hasNext(); ) {
301                            Way w = (Way) ds.getPrimitiveById(it.next(), OsmPrimitiveType.WAY);
302                            if (w != null && w.getNodesCount() > 0) { // fix #7173 (empty ways on purge)
303                                waysToJoin.add(w);
304                            }
305                        }
306                        nodes.addAll(joinWays(waysToJoin).iterator().next().getNodes());
307                    }
308                    resetPoly();
309                }
310            }
311            
312            private void resetPoly() {
313                poly.reset();
314                buildPoly();
315                bounds = null;
316            }
317            
318            public void nodeMoved(NodeMovedEvent event) {
319                final Node n = event.getNode();
320                boolean innerChanged = false;
321                for (PolyData inner : inners) {
322                    if (inner.nodes.contains(n)) {
323                        inner.resetPoly();
324                        innerChanged = true;
325                    }
326                }
327                if (nodes.contains(n) || innerChanged) {
328                    resetPoly();
329                }
330            }
331            
332            public void wayNodesChanged(WayNodesChangedEvent event) {
333                final Long wayId = event.getChangedWay().getUniqueId();
334                boolean innerChanged = false;
335                for (PolyData inner : inners) {
336                    if (inner.wayIds.contains(wayId)) {
337                        inner.resetNodes(event.getDataset());
338                        innerChanged = true;
339                    }
340                }
341                if (wayIds.contains(wayId) || innerChanged) {
342                    resetNodes(event.getDataset());
343                }
344            }
345        }
346    
347        private final List<Way> innerWays = new ArrayList<Way>();
348        private final List<Way> outerWays = new ArrayList<Way>();
349        private final List<PolyData> innerPolygons = new ArrayList<PolyData>();
350        private final List<PolyData> outerPolygons = new ArrayList<PolyData>();
351        private final List<PolyData> combinedPolygons = new ArrayList<PolyData>();
352        
353        private boolean incomplete;
354    
355        public Multipolygon(Relation r) {
356            load(r);
357        }
358    
359        private void load(Relation r) {
360            MultipolygonRoleMatcher matcher = getMultipolygonRoleMatcher();
361    
362            // Fill inner and outer list with valid ways
363            for (RelationMember m : r.getMembers()) {
364                if (m.getMember().isIncomplete()) {
365                    this.incomplete = true;
366                } else if (m.getMember().isDrawable()) {
367                    if (m.isWay()) {
368                        Way w = m.getWay();
369    
370                        if (w.getNodesCount() < 2) {
371                            continue;
372                        }
373    
374                        if (matcher.isInnerRole(m.getRole())) {
375                            innerWays.add(w);
376                        } else if (matcher.isOuterRole(m.getRole())) {
377                            outerWays.add(w);
378                        } else if (!m.hasRole()) {
379                            outerWays.add(w);
380                        } // Remaining roles ignored
381                    } // Non ways ignored
382                }
383            }
384    
385            createPolygons(innerWays, innerPolygons);
386            createPolygons(outerWays, outerPolygons);
387            if (!outerPolygons.isEmpty()) {
388                addInnerToOuters();
389            }
390        }
391        
392        public final boolean isIncomplete() {
393            return incomplete;
394        }
395    
396        private void createPolygons(List<Way> ways, List<PolyData> result) {
397            List<Way> waysToJoin = new ArrayList<Way>();
398            for (Way way: ways) {
399                if (way.isClosed()) {
400                    result.add(new PolyData(way));
401                } else {
402                    waysToJoin.add(way);
403                }
404            }
405    
406            for (JoinedWay jw: joinWays(waysToJoin)) {
407                result.add(new PolyData(jw));
408            }
409        }
410    
411        public static Collection<JoinedWay> joinWays(Collection<Way> waysToJoin)
412        {
413            final Collection<JoinedWay> result = new ArrayList<JoinedWay>();
414            final Way[] joinArray = waysToJoin.toArray(new Way[waysToJoin.size()]);
415            int left = waysToJoin.size();
416            while (left > 0) {
417                Way w = null;
418                boolean selected = false;
419                List<Node> nodes = null;
420                Set<Long> wayIds = new HashSet<Long>();
421                boolean joined = true;
422                while (joined && left > 0) {
423                    joined = false;
424                    for (int i = 0; i < joinArray.length && left != 0; ++i) {
425                        if (joinArray[i] != null) {
426                            Way c = joinArray[i];
427                            if (w == null) {
428                                w = c;
429                                selected = w.isSelected();
430                                joinArray[i] = null;
431                                --left;
432                            } else {
433                                int mode = 0;
434                                int cl = c.getNodesCount()-1;
435                                int nl;
436                                if (nodes == null) {
437                                    nl = w.getNodesCount()-1;
438                                    if (w.getNode(nl) == c.getNode(0)) {
439                                        mode = 21;
440                                    } else if (w.getNode(nl) == c.getNode(cl)) {
441                                        mode = 22;
442                                    } else if (w.getNode(0) == c.getNode(0)) {
443                                        mode = 11;
444                                    } else if (w.getNode(0) == c.getNode(cl)) {
445                                        mode = 12;
446                                    }
447                                } else {
448                                    nl = nodes.size()-1;
449                                    if (nodes.get(nl) == c.getNode(0)) {
450                                        mode = 21;
451                                    } else if (nodes.get(0) == c.getNode(cl)) {
452                                        mode = 12;
453                                    } else if (nodes.get(0) == c.getNode(0)) {
454                                        mode = 11;
455                                    } else if (nodes.get(nl) == c.getNode(cl)) {
456                                        mode = 22;
457                                    }
458                                }
459                                if (mode != 0) {
460                                    joinArray[i] = null;
461                                    joined = true;
462                                    if (c.isSelected()) {
463                                        selected = true;
464                                    }
465                                    --left;
466                                    if (nodes == null) {
467                                        nodes = w.getNodes();
468                                        wayIds.add(w.getUniqueId());
469                                    }
470                                    nodes.remove((mode == 21 || mode == 22) ? nl : 0);
471                                    if (mode == 21) {
472                                        nodes.addAll(c.getNodes());
473                                    } else if (mode == 12) {
474                                        nodes.addAll(0, c.getNodes());
475                                    } else if (mode == 22) {
476                                        for (Node node : c.getNodes()) {
477                                            nodes.add(nl, node);
478                                        }
479                                    } else /* mode == 11 */ {
480                                        for (Node node : c.getNodes()) {
481                                            nodes.add(0, node);
482                                        }
483                                    }
484                                    wayIds.add(c.getUniqueId());
485                                }
486                            }
487                        }
488                    } /* for(i = ... */
489                } /* while(joined) */
490    
491                if (nodes == null) {
492                    nodes = w.getNodes();
493                    wayIds.add(w.getUniqueId());
494                }
495    
496                result.add(new JoinedWay(nodes, wayIds, selected));
497            } /* while(left != 0) */
498    
499            return result;
500        }
501    
502        public PolyData findOuterPolygon(PolyData inner, List<PolyData> outerPolygons) {
503    
504            // First try to test only bbox, use precise testing only if we don't get unique result
505            Rectangle2D innerBox = inner.getBounds();
506            PolyData insidePolygon = null;
507            PolyData intersectingPolygon = null;
508            int insideCount = 0;
509            int intersectingCount = 0;
510    
511            for (PolyData outer: outerPolygons) {
512                if (outer.getBounds().contains(innerBox)) {
513                    insidePolygon = outer;
514                    insideCount++;
515                } else if (outer.getBounds().intersects(innerBox)) {
516                    intersectingPolygon = outer;
517                    intersectingCount++;
518                }
519            }
520            
521            if (insideCount == 1)
522                return insidePolygon;
523            else if (intersectingCount == 1)
524                return intersectingPolygon;
525    
526            PolyData result = null;
527            for (PolyData combined : outerPolygons) {
528                Intersection c = combined.contains(inner.poly);
529                if (c != Intersection.OUTSIDE)
530                {
531                    if (result == null || result.contains(combined.poly) != Intersection.INSIDE) {
532                        result = combined;
533                    }
534                }
535            }
536            return result;
537        }
538    
539        private void addInnerToOuters()  {
540    
541            if (innerPolygons.isEmpty()) {
542                combinedPolygons.addAll(outerPolygons);
543            } else if (outerPolygons.size() == 1) {
544                PolyData combinedOuter = new PolyData(outerPolygons.get(0));
545                for (PolyData inner: innerPolygons) {
546                    combinedOuter.addInner(inner);
547                }
548                combinedPolygons.add(combinedOuter);
549            } else {
550                for (PolyData outer: outerPolygons) {
551                    combinedPolygons.add(new PolyData(outer));
552                }
553    
554                for (PolyData pdInner: innerPolygons) {
555                    PolyData o = findOuterPolygon(pdInner, combinedPolygons);
556                    if (o == null) {
557                        o = outerPolygons.get(0);
558                    }
559                    o.addInner(pdInner);
560                }
561            }
562            
563            // Clear inner and outer polygons to reduce memory footprint
564            innerPolygons.clear();
565            outerPolygons.clear();
566        }
567    
568        public List<Way> getOuterWays() {
569            return outerWays;
570        }
571    
572        public List<Way> getInnerWays() {
573            return innerWays;
574        }
575    /*
576        public List<PolyData> getInnerPolygons() {
577            return innerPolygons;
578        }
579    
580        public List<PolyData> getOuterPolygons() {
581            return outerPolygons;
582        }
583    */
584        public List<PolyData> getCombinedPolygons() {
585            return combinedPolygons;
586        }
587    }