001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data.osm;
003
004import static org.openstreetmap.josm.tools.I18n.tr;
005
006import java.util.ArrayList;
007import java.util.Collection;
008import java.util.Collections;
009import java.util.HashSet;
010import java.util.List;
011import java.util.Set;
012
013import org.openstreetmap.josm.tools.Geometry;
014import org.openstreetmap.josm.tools.Geometry.PolygonIntersection;
015import org.openstreetmap.josm.tools.MultiMap;
016
017public 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 the way to form the polygon
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 list of nodes
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 {@link #innerWays} and {@link #outerWays} to the result.
106     * TODO: Currently cannot process touching polygons. See code in JoinAreasAction.
107     * @param ways ways to analyze
108     * @return error description if the ways cannot be split, {@code null} if all fine.
109     */
110    public String makeFromWays(Collection<Way> ways){
111        List<JoinedPolygon> joinedWays = new ArrayList<JoinedPolygon>();
112
113        //collect ways connecting to each node.
114        MultiMap<Node, Way> nodesWithConnectedWays = new MultiMap<Node, Way>();
115        Set<Way> usedWays = new HashSet<Way>();
116
117        for(Way w: ways) {
118            if (w.getNodesCount() < 2) {
119                return tr("Cannot add a way with only {0} nodes.", w.getNodesCount());
120            }
121
122            if (w.isClosed()) {
123                //closed way, add as is.
124                JoinedPolygon jw = new JoinedPolygon(w);
125                joinedWays.add(jw);
126                usedWays.add(w);
127            }
128            else {
129                nodesWithConnectedWays.put(w.lastNode(), w);
130                nodesWithConnectedWays.put(w.firstNode(), w);
131            }
132        }
133
134        //process unclosed ways
135        for (Way startWay: ways) {
136            if (usedWays.contains(startWay)){
137                continue;
138            }
139
140            Node startNode = startWay.firstNode();
141            List<Way> collectedWays = new ArrayList<Way>();
142            List<Boolean> collectedWaysReverse = new ArrayList<Boolean>();
143            Way curWay = startWay;
144            Node prevNode = startNode;
145
146            //find polygon ways
147            while (true) {
148                boolean curWayReverse = prevNode == curWay.lastNode();
149                Node nextNode = (curWayReverse) ? curWay.firstNode(): curWay.lastNode();
150
151                //add cur way to the list
152                collectedWays.add(curWay);
153                collectedWaysReverse.add(Boolean.valueOf(curWayReverse));
154
155                if (nextNode == startNode) {
156                    //way finished
157                    break;
158                }
159
160                //find next way
161                Collection<Way> adjacentWays = nodesWithConnectedWays.get(nextNode);
162
163                if (adjacentWays.size() != 2) {
164                    return tr("Each node must connect exactly 2 ways");
165                }
166
167                Way nextWay = null;
168                for(Way way: adjacentWays){
169                    if (way != curWay){
170                        nextWay = way;
171                    }
172                }
173
174                //move to the next way
175                curWay = nextWay;
176                prevNode = nextNode;
177            }
178
179            usedWays.addAll(collectedWays);
180            joinedWays.add(new JoinedPolygon(collectedWays, collectedWaysReverse));
181        }
182
183        //analyze witch way is inside witch outside.
184        return makeFromPolygons(joinedWays);
185    }
186
187    /**
188     * This method analyzes which ways are inner and which outer. Sets {@link #innerWays} and {@link #outerWays} to the result.
189     * @param polygons polygons to analyze
190     * @return error description if the ways cannot be split, {@code null} if all fine.
191     */
192    private String makeFromPolygons(List<JoinedPolygon> polygons) {
193        List<PolygonLevel> list = findOuterWaysRecursive(0, polygons);
194
195        if (list == null){
196            return tr("There is an intersection between ways.");
197        }
198
199        this.outerWays = new ArrayList<JoinedPolygon>(0);
200        this.innerWays = new ArrayList<JoinedPolygon>(0);
201
202        //take every other level
203        for (PolygonLevel pol : list) {
204            if (pol.level % 2 == 0) {
205                this.outerWays.add(pol.outerWay);
206            }
207            else {
208                this.innerWays.add(pol.outerWay);
209            }
210        }
211
212        return null;
213    }
214
215    /**
216     * Collects outer way and corresponding inner ways from all boundaries.
217     * @param boundaryWays
218     * @return the outermostWay, or {@code null} if intersection found.
219     */
220    private List<PolygonLevel> findOuterWaysRecursive(int level, Collection<JoinedPolygon> boundaryWays) {
221
222        //TODO: bad performance for deep nesting...
223        List<PolygonLevel> result = new ArrayList<PolygonLevel>();
224
225        for (JoinedPolygon outerWay : boundaryWays) {
226
227            boolean outerGood = true;
228            List<JoinedPolygon> innerCandidates = new ArrayList<JoinedPolygon>();
229
230            for (JoinedPolygon innerWay : boundaryWays) {
231                if (innerWay == outerWay) {
232                    continue;
233                }
234
235                PolygonIntersection intersection = Geometry.polygonIntersection(outerWay.nodes, innerWay.nodes);
236
237                if (intersection == PolygonIntersection.FIRST_INSIDE_SECOND) {
238                    outerGood = false;  // outer is inside another polygon
239                    break;
240                } else if (intersection == PolygonIntersection.SECOND_INSIDE_FIRST) {
241                    innerCandidates.add(innerWay);
242                }
243                else if (intersection == PolygonIntersection.CROSSING)
244                {
245                    //ways intersect
246                    return null;
247                }
248            }
249
250            if (!outerGood) {
251                continue;
252            }
253
254            //add new outer polygon
255            PolygonLevel pol = new PolygonLevel(outerWay, level);
256
257            //process inner ways
258            if (!innerCandidates.isEmpty()) {
259                List<PolygonLevel> innerList = this.findOuterWaysRecursive(level + 1, innerCandidates);
260                if (innerList == null) {
261                    return null; //intersection found
262                }
263
264                result.addAll(innerList);
265
266                for (PolygonLevel pl : innerList) {
267                    if (pl.level == level + 1) {
268                        pol.innerWays.add(pl.outerWay);
269                    }
270                }
271            }
272
273            result.add(pol);
274        }
275
276        return result;
277    }
278}