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.awt.geom.Area;
007import java.util.ArrayList;
008import java.util.Collection;
009import java.util.Collections;
010import java.util.HashSet;
011import java.util.List;
012import java.util.Set;
013
014import org.openstreetmap.josm.tools.Geometry;
015import org.openstreetmap.josm.tools.Geometry.PolygonIntersection;
016import org.openstreetmap.josm.tools.MultiMap;
017
018public class MultipolygonCreate {
019
020    /**
021     * Represents one polygon that consists of multiple ways.
022     * @author Viesturs
023     *
024     */
025    public static class JoinedPolygon {
026        public final List<Way> ways;
027        public final List<Boolean> reversed;
028        public final List<Node> nodes;
029        public final Area area;
030
031        public JoinedPolygon(List<Way> ways, List<Boolean> reversed) {
032            this.ways = ways;
033            this.reversed = reversed;
034            this.nodes = this.getNodes();
035            this.area = Geometry.getArea(nodes);
036        }
037
038        /**
039         * Creates a polygon from single way.
040         * @param way the way to form the polygon
041         */
042        public JoinedPolygon(Way way) {
043            this(Collections.singletonList(way), Collections.singletonList(Boolean.FALSE));
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        public List<Node> getNodes() {
051            List<Node> nodes = new ArrayList<>();
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<>();
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<>(0);
101        this.innerWays = new ArrayList<>(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        try {
112            List<JoinedPolygon> joinedWays = joinWays(ways);
113            //analyze witch way is inside witch outside.
114            return makeFromPolygons(joinedWays);
115        } catch (JoinedPolygonCreationException ex) {
116            return ex.getMessage();
117        }
118    }
119
120    /**
121     * An exception indicating an error while joining ways to multipolygon rings.
122     */
123    public static class JoinedPolygonCreationException extends RuntimeException {
124        public JoinedPolygonCreationException(String message) {
125            super(message);
126        }
127    }
128
129    /**
130     * Joins the given {@code ways} to multipolygon rings.
131     * @param ways the ways to join.
132     * @return a list of multipolygon rings.
133     * @throws JoinedPolygonCreationException if the creation fails.
134     */
135    public static List<JoinedPolygon> joinWays(Collection<Way> ways) throws JoinedPolygonCreationException {
136        List<JoinedPolygon> joinedWays = new ArrayList<>();
137
138        //collect ways connecting to each node.
139        MultiMap<Node, Way> nodesWithConnectedWays = new MultiMap<>();
140        Set<Way> usedWays = new HashSet<>();
141
142        for(Way w: ways) {
143            if (w.getNodesCount() < 2) {
144                throw new JoinedPolygonCreationException(tr("Cannot add a way with only {0} nodes.", w.getNodesCount()));
145            }
146
147            if (w.isClosed()) {
148                //closed way, add as is.
149                JoinedPolygon jw = new JoinedPolygon(w);
150                joinedWays.add(jw);
151                usedWays.add(w);
152            }
153            else {
154                nodesWithConnectedWays.put(w.lastNode(), w);
155                nodesWithConnectedWays.put(w.firstNode(), w);
156            }
157        }
158
159        //process unclosed ways
160        for (Way startWay: ways) {
161            if (usedWays.contains(startWay)){
162                continue;
163            }
164
165            Node startNode = startWay.firstNode();
166            List<Way> collectedWays = new ArrayList<>();
167            List<Boolean> collectedWaysReverse = new ArrayList<>();
168            Way curWay = startWay;
169            Node prevNode = startNode;
170
171            //find polygon ways
172            while (true) {
173                boolean curWayReverse = prevNode == curWay.lastNode();
174                Node nextNode = (curWayReverse) ? curWay.firstNode(): curWay.lastNode();
175
176                //add cur way to the list
177                collectedWays.add(curWay);
178                collectedWaysReverse.add(Boolean.valueOf(curWayReverse));
179
180                if (nextNode == startNode) {
181                    //way finished
182                    break;
183                }
184
185                //find next way
186                Collection<Way> adjacentWays = nodesWithConnectedWays.get(nextNode);
187
188                if (adjacentWays.size() != 2) {
189                    throw new JoinedPolygonCreationException(tr("Each node must connect exactly 2 ways"));
190                }
191
192                Way nextWay = null;
193                for(Way way: adjacentWays){
194                    if (way != curWay){
195                        nextWay = way;
196                    }
197                }
198
199                //move to the next way
200                curWay = nextWay;
201                prevNode = nextNode;
202            }
203
204            usedWays.addAll(collectedWays);
205            joinedWays.add(new JoinedPolygon(collectedWays, collectedWaysReverse));
206        }
207
208        return joinedWays;
209    }
210
211    /**
212     * This method analyzes which ways are inner and which outer. Sets {@link #innerWays} and {@link #outerWays} to the result.
213     * @param polygons polygons to analyze
214     * @return error description if the ways cannot be split, {@code null} if all fine.
215     */
216    private String makeFromPolygons(List<JoinedPolygon> polygons) {
217        List<PolygonLevel> list = findOuterWaysRecursive(0, polygons);
218
219        if (list == null){
220            return tr("There is an intersection between ways.");
221        }
222
223        this.outerWays = new ArrayList<>(0);
224        this.innerWays = new ArrayList<>(0);
225
226        //take every other level
227        for (PolygonLevel pol : list) {
228            if (pol.level % 2 == 0) {
229                this.outerWays.add(pol.outerWay);
230            }
231            else {
232                this.innerWays.add(pol.outerWay);
233            }
234        }
235
236        return null;
237    }
238
239    /**
240     * Collects outer way and corresponding inner ways from all boundaries.
241     * @param boundaryWays
242     * @return the outermostWay, or {@code null} if intersection found.
243     */
244    private List<PolygonLevel> findOuterWaysRecursive(int level, Collection<JoinedPolygon> boundaryWays) {
245
246        //TODO: bad performance for deep nesting...
247        List<PolygonLevel> result = new ArrayList<>();
248
249        for (JoinedPolygon outerWay : boundaryWays) {
250
251            boolean outerGood = true;
252            List<JoinedPolygon> innerCandidates = new ArrayList<>();
253
254            for (JoinedPolygon innerWay : boundaryWays) {
255                if (innerWay == outerWay) {
256                    continue;
257                }
258
259                PolygonIntersection intersection = Geometry.polygonIntersection(outerWay.area, innerWay.area);
260
261                if (intersection == PolygonIntersection.FIRST_INSIDE_SECOND) {
262                    outerGood = false;  // outer is inside another polygon
263                    break;
264                } else if (intersection == PolygonIntersection.SECOND_INSIDE_FIRST) {
265                    innerCandidates.add(innerWay);
266                }
267                else if (intersection == PolygonIntersection.CROSSING)
268                {
269                    //ways intersect
270                    return null;
271                }
272            }
273
274            if (!outerGood) {
275                continue;
276            }
277
278            //add new outer polygon
279            PolygonLevel pol = new PolygonLevel(outerWay, level);
280
281            //process inner ways
282            if (!innerCandidates.isEmpty()) {
283                List<PolygonLevel> innerList = this.findOuterWaysRecursive(level + 1, innerCandidates);
284                if (innerList == null) {
285                    return null; //intersection found
286                }
287
288                result.addAll(innerList);
289
290                for (PolygonLevel pl : innerList) {
291                    if (pl.level == level + 1) {
292                        pol.innerWays.add(pl.outerWay);
293                    }
294                }
295            }
296
297            result.add(pol);
298        }
299
300        return result;
301    }
302}