001    // License: GPL. For details, see LICENSE file.
002    package org.openstreetmap.josm.data.osm;
003    
004    import static org.openstreetmap.josm.tools.I18n.tr;
005    
006    import java.util.ArrayList;
007    import java.util.Collection;
008    import java.util.Collections;
009    import java.util.HashSet;
010    import java.util.List;
011    import java.util.Set;
012    
013    import org.openstreetmap.josm.tools.Geometry;
014    import org.openstreetmap.josm.tools.Geometry.PolygonIntersection;
015    import org.openstreetmap.josm.tools.MultiMap;
016    
017    public class MultipolygonCreate {
018    
019        /**
020         * Represents one polygon that consists of multiple ways.
021         * @author Viesturs
022         *
023         */
024        public static class JoinedPolygon {
025            public final List<Way> ways;
026            public final List<Boolean> reversed;
027            public final List<Node> nodes;
028    
029            public JoinedPolygon(List<Way> ways, List<Boolean> reversed) {
030                this.ways = ways;
031                this.reversed = reversed;
032                this.nodes = this.getNodes();
033            }
034    
035            /**
036             * Creates a polygon from single way.
037             * @param way
038             */
039            public JoinedPolygon(Way way) {
040                this.ways = Collections.singletonList(way);
041                this.reversed = Collections.singletonList(Boolean.FALSE);
042                this.nodes = this.getNodes();
043            }
044    
045    
046            /**
047             * Builds a list of nodes for this polygon. First node is not duplicated as last node.
048             * @return
049             */
050            private List<Node> getNodes() {
051                List<Node> nodes = new ArrayList<Node>();
052    
053                for(int waypos = 0; waypos < this.ways.size(); waypos ++) {
054                    Way way = this.ways.get(waypos);
055                    boolean reversed = this.reversed.get(waypos).booleanValue();
056    
057                    if (!reversed){
058                        for (int pos = 0; pos < way.getNodesCount() - 1; pos++) {
059                            nodes.add(way.getNode(pos));
060                        }
061                    }
062                    else {
063                        for (int pos = way.getNodesCount() - 1; pos > 0; pos--) {
064                            nodes.add(way.getNode(pos));
065                        }
066                    }
067                }
068    
069                return nodes;
070            }
071        }
072    
073    
074        /**
075         * Helper storage class for finding findOuterWays
076         * @author viesturs
077         */
078        static class PolygonLevel {
079            public final int level; //nesting level , even for outer, odd for inner polygons.
080            public final JoinedPolygon outerWay;
081    
082            public List<JoinedPolygon> innerWays;
083    
084            public PolygonLevel(JoinedPolygon _pol, int _level) {
085                this.outerWay = _pol;
086                this.level = _level;
087                this.innerWays = new ArrayList<JoinedPolygon>();
088            }
089        }
090    
091        public List<JoinedPolygon> outerWays;
092        public List<JoinedPolygon> innerWays;
093    
094        public MultipolygonCreate(List<JoinedPolygon> outerWays, List<JoinedPolygon> innerWays){
095            this.outerWays = outerWays;
096            this.innerWays = innerWays;
097        }
098    
099        public MultipolygonCreate(){
100            this.outerWays = new ArrayList<JoinedPolygon>(0);
101            this.innerWays = new ArrayList<JoinedPolygon>(0);
102        }
103    
104        /**
105         * Splits ways into inner and outer JoinedWays. Sets innerWays and outerWays to the result.
106         *  TODO: Currently cannot process touching polygons. See code in JoinAreasAction.
107         * @return error description if the ways cannot be split. Null if all fine.
108         */
109        public String makeFromWays(Collection<Way> ways){
110            List<JoinedPolygon> joinedWays = new ArrayList<JoinedPolygon>();
111    
112            //collect ways connecting to each node.
113            MultiMap<Node, Way> nodesWithConnectedWays = new MultiMap<Node, Way>();
114            Set<Way> usedWays = new HashSet<Way>();
115    
116            for(Way w: ways) {
117                if (w.getNodesCount() < 2) {
118                    return tr("Cannot add a way with only {0} nodes.", w.getNodesCount());
119                }
120    
121                if (w.isClosed()) {
122                    //closed way, add as is.
123                    JoinedPolygon jw = new JoinedPolygon(w);
124                    joinedWays.add(jw);
125                    usedWays.add(w);
126                }
127                else {
128                    nodesWithConnectedWays.put(w.lastNode(), w);
129                    nodesWithConnectedWays.put(w.firstNode(), w);
130                }
131            }
132    
133            //process unclosed ways
134            for (Way startWay: ways) {
135                if (usedWays.contains(startWay)){
136                    continue;
137                }
138    
139                Node startNode = startWay.firstNode();
140                List<Way> collectedWays = new ArrayList<Way>();
141                List<Boolean> collectedWaysReverse = new ArrayList<Boolean>();
142                Way curWay = startWay;
143                Node prevNode = startNode;
144    
145                //find polygon ways
146                while (true) {
147                    boolean curWayReverse = prevNode == curWay.lastNode();
148                    Node nextNode = (curWayReverse) ? curWay.firstNode(): curWay.lastNode();
149    
150                    //add cur way to the list
151                    collectedWays.add(curWay);
152                    collectedWaysReverse.add(Boolean.valueOf(curWayReverse));
153    
154                    if (nextNode == startNode) {
155                        //way finished
156                        break;
157                    }
158    
159                    //find next way
160                    Collection<Way> adjacentWays = nodesWithConnectedWays.get(nextNode);
161    
162                    if (adjacentWays.size() != 2) {
163                        return tr("Each node must connect exactly 2 ways");
164                    }
165    
166                    Way nextWay = null;
167                    for(Way way: adjacentWays){
168                        if (way != curWay){
169                            nextWay = way;
170                        }
171                    }
172    
173                    //move to the next way
174                    curWay = nextWay;
175                    prevNode = nextNode;
176                }
177    
178                usedWays.addAll(collectedWays);
179                joinedWays.add(new JoinedPolygon(collectedWays, collectedWaysReverse));
180            }
181    
182            //analyze witch way is inside witch outside.
183            return makeFromPolygons(joinedWays);
184        }
185    
186        /**
187         * This method analyzes which ways are inner and which outer. Sets innerWays and outerWays to the result.
188         * @param joinedWays
189         * @return error description if the ways cannot be split. Null if all fine.
190         */
191        private String makeFromPolygons(List<JoinedPolygon> polygons) {
192            List<PolygonLevel> list = findOuterWaysRecursive(0, polygons);
193    
194            if (list == null){
195                return tr("There is an intersection between ways.");
196            }
197    
198            this.outerWays = new ArrayList<JoinedPolygon>(0);
199            this.innerWays = new ArrayList<JoinedPolygon>(0);
200    
201            //take every other level
202            for (PolygonLevel pol : list) {
203                if (pol.level % 2 == 0) {
204                    this.outerWays.add(pol.outerWay);
205                }
206                else {
207                    this.innerWays.add(pol.outerWay);
208                }
209            }
210    
211            return null;
212        }
213    
214        /**
215         * Collects outer way and corresponding inner ways from all boundaries.
216         * @param boundaryWays
217         * @return the outermostWay, or null if intersection found.
218         */
219        private List<PolygonLevel> findOuterWaysRecursive(int level, Collection<JoinedPolygon> boundaryWays) {
220    
221            //TODO: bad performance for deep nesting...
222            List<PolygonLevel> result = new ArrayList<PolygonLevel>();
223    
224            for (JoinedPolygon outerWay : boundaryWays) {
225    
226                boolean outerGood = true;
227                List<JoinedPolygon> innerCandidates = new ArrayList<JoinedPolygon>();
228    
229                for (JoinedPolygon innerWay : boundaryWays) {
230                    if (innerWay == outerWay) {
231                        continue;
232                    }
233    
234                    PolygonIntersection intersection = Geometry.polygonIntersection(outerWay.nodes, innerWay.nodes);
235    
236                    if (intersection == PolygonIntersection.FIRST_INSIDE_SECOND) {
237                        outerGood = false;  // outer is inside another polygon
238                        break;
239                    } else if (intersection == PolygonIntersection.SECOND_INSIDE_FIRST) {
240                        innerCandidates.add(innerWay);
241                    }
242                    else if (intersection == PolygonIntersection.CROSSING)
243                    {
244                        //ways intersect
245                        return null;
246                    }
247                }
248    
249                if (!outerGood) {
250                    continue;
251                }
252    
253                //add new outer polygon
254                PolygonLevel pol = new PolygonLevel(outerWay, level);
255    
256                //process inner ways
257                if (innerCandidates.size() > 0) {
258                    List<PolygonLevel> innerList = this.findOuterWaysRecursive(level + 1, innerCandidates);
259                    if (innerList == null) {
260                        return null; //intersection found
261                    }
262    
263                    result.addAll(innerList);
264    
265                    for (PolygonLevel pl : innerList) {
266                        if (pl.level == level + 1) {
267                            pol.innerWays.add(pl.outerWay);
268                        }
269                    }
270                }
271    
272                result.add(pol);
273            }
274    
275            return result;
276        }
277    }