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    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                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<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                    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<Way>();
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<Way>();
350    private final List<Way> outerWays = new ArrayList<Way>();
351    private final List<PolyData> innerPolygons = new ArrayList<PolyData>();
352    private final List<PolyData> outerPolygons = new ArrayList<PolyData>();
353    private final List<PolyData> combinedPolygons = new ArrayList<PolyData>();
354
355    private boolean incomplete;
356
357    public Multipolygon(Relation r) {
358        load(r);
359    }
360
361    private 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<Way>();
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    {
415        final Collection<JoinedWay> result = new ArrayList<JoinedWay>();
416        final Way[] joinArray = waysToJoin.toArray(new Way[waysToJoin.size()]);
417        int left = waysToJoin.size();
418        while (left > 0) {
419            Way w = null;
420            boolean selected = false;
421            List<Node> nodes = null;
422            Set<Long> wayIds = new HashSet<Long>();
423            boolean joined = true;
424            while (joined && left > 0) {
425                joined = false;
426                for (int i = 0; i < joinArray.length && left != 0; ++i) {
427                    if (joinArray[i] != null) {
428                        Way c = joinArray[i];
429                        if (w == null) {
430                            w = c;
431                            selected = w.isSelected();
432                            joinArray[i] = null;
433                            --left;
434                        } else {
435                            int mode = 0;
436                            int cl = c.getNodesCount()-1;
437                            int nl;
438                            if (nodes == null) {
439                                nl = w.getNodesCount()-1;
440                                if (w.getNode(nl) == c.getNode(0)) {
441                                    mode = 21;
442                                } else if (w.getNode(nl) == c.getNode(cl)) {
443                                    mode = 22;
444                                } else if (w.getNode(0) == c.getNode(0)) {
445                                    mode = 11;
446                                } else if (w.getNode(0) == c.getNode(cl)) {
447                                    mode = 12;
448                                }
449                            } else {
450                                nl = nodes.size()-1;
451                                if (nodes.get(nl) == c.getNode(0)) {
452                                    mode = 21;
453                                } else if (nodes.get(0) == c.getNode(cl)) {
454                                    mode = 12;
455                                } else if (nodes.get(0) == c.getNode(0)) {
456                                    mode = 11;
457                                } else if (nodes.get(nl) == c.getNode(cl)) {
458                                    mode = 22;
459                                }
460                            }
461                            if (mode != 0) {
462                                joinArray[i] = null;
463                                joined = true;
464                                if (c.isSelected()) {
465                                    selected = true;
466                                }
467                                --left;
468                                if (nodes == null) {
469                                    nodes = w.getNodes();
470                                    wayIds.add(w.getUniqueId());
471                                }
472                                nodes.remove((mode == 21 || mode == 22) ? nl : 0);
473                                if (mode == 21) {
474                                    nodes.addAll(c.getNodes());
475                                } else if (mode == 12) {
476                                    nodes.addAll(0, c.getNodes());
477                                } else if (mode == 22) {
478                                    for (Node node : c.getNodes()) {
479                                        nodes.add(nl, node);
480                                    }
481                                } else /* mode == 11 */ {
482                                    for (Node node : c.getNodes()) {
483                                        nodes.add(0, node);
484                                    }
485                                }
486                                wayIds.add(c.getUniqueId());
487                            }
488                        }
489                    }
490                }
491            }
492
493            if (nodes == null) {
494                nodes = w.getNodes();
495                wayIds.add(w.getUniqueId());
496            }
497
498            result.add(new JoinedWay(nodes, wayIds, selected));
499        }
500
501        return result;
502    }
503
504    public PolyData findOuterPolygon(PolyData inner, List<PolyData> outerPolygons) {
505
506        // First try to test only bbox, use precise testing only if we don't get unique result
507        Rectangle2D innerBox = inner.getBounds();
508        PolyData insidePolygon = null;
509        PolyData intersectingPolygon = null;
510        int insideCount = 0;
511        int intersectingCount = 0;
512
513        for (PolyData outer: outerPolygons) {
514            if (outer.getBounds().contains(innerBox)) {
515                insidePolygon = outer;
516                insideCount++;
517            } else if (outer.getBounds().intersects(innerBox)) {
518                intersectingPolygon = outer;
519                intersectingCount++;
520            }
521        }
522
523        if (insideCount == 1)
524            return insidePolygon;
525        else if (intersectingCount == 1)
526            return intersectingPolygon;
527
528        PolyData result = null;
529        for (PolyData combined : outerPolygons) {
530            Intersection c = combined.contains(inner.poly);
531            if (c != Intersection.OUTSIDE)
532            {
533                if (result == null || result.contains(combined.poly) != Intersection.INSIDE) {
534                    result = combined;
535                }
536            }
537        }
538        return result;
539    }
540
541    private 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}