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.Rectangle;
007import java.awt.geom.Area;
008import java.io.IOException;
009import java.io.ObjectInputStream;
010import java.io.ObjectOutputStream;
011import java.util.ArrayList;
012import java.util.Collection;
013import java.util.Collections;
014import java.util.HashSet;
015import java.util.List;
016import java.util.Set;
017import java.util.concurrent.ForkJoinPool;
018import java.util.concurrent.ForkJoinTask;
019import java.util.concurrent.RecursiveTask;
020
021import org.openstreetmap.josm.Main;
022import org.openstreetmap.josm.tools.Geometry;
023import org.openstreetmap.josm.tools.Geometry.PolygonIntersection;
024import org.openstreetmap.josm.tools.MultiMap;
025import org.openstreetmap.josm.tools.Pair;
026import org.openstreetmap.josm.tools.Utils;
027
028/**
029 * Helper class to build multipolygons from multiple ways.
030 * @author viesturs
031 * @since 7392 (rename)
032 * @since 3704
033 */
034public class MultipolygonBuilder {
035
036    private static final ForkJoinPool THREAD_POOL =
037            Utils.newForkJoinPool("multipolygon_creation.numberOfThreads", "multipolygon-builder-%d", Thread.NORM_PRIORITY);
038
039    /**
040     * Represents one polygon that consists of multiple ways.
041     */
042    public static class JoinedPolygon {
043        public final List<Way> ways;
044        public final List<Boolean> reversed;
045        public final List<Node> nodes;
046        public final Area area;
047        public final Rectangle bounds;
048
049        /**
050         * Constructs a new {@code JoinedPolygon} from given list of ways.
051         * @param ways The ways used to build joined polygon
052         * @param reversed list of reversed states
053         */
054        public JoinedPolygon(List<Way> ways, List<Boolean> reversed) {
055            this.ways = ways;
056            this.reversed = reversed;
057            this.nodes = this.getNodes();
058            this.area = Geometry.getArea(nodes);
059            this.bounds = area.getBounds();
060        }
061
062        /**
063         * Creates a polygon from single way.
064         * @param way the way to form the polygon
065         */
066        public JoinedPolygon(Way way) {
067            this(Collections.singletonList(way), Collections.singletonList(Boolean.FALSE));
068        }
069
070        /**
071         * Builds a list of nodes for this polygon. First node is not duplicated as last node.
072         * @return list of nodes
073         */
074        public List<Node> getNodes() {
075            List<Node> nodes = new ArrayList<>();
076
077            for (int waypos = 0; waypos < this.ways.size(); waypos++) {
078                Way way = this.ways.get(waypos);
079                boolean reversed = this.reversed.get(waypos).booleanValue();
080
081                if (!reversed) {
082                    for (int pos = 0; pos < way.getNodesCount() - 1; pos++) {
083                        nodes.add(way.getNode(pos));
084                    }
085                } else {
086                    for (int pos = way.getNodesCount() - 1; pos > 0; pos--) {
087                        nodes.add(way.getNode(pos));
088                    }
089                }
090            }
091
092            return nodes;
093        }
094    }
095
096    /**
097     * Helper storage class for finding findOuterWays
098     */
099    static class PolygonLevel {
100        public final int level; // nesting level, even for outer, odd for inner polygons.
101        public final JoinedPolygon outerWay;
102
103        public List<JoinedPolygon> innerWays;
104
105        PolygonLevel(JoinedPolygon pol, int level) {
106            this.outerWay = pol;
107            this.level = level;
108            this.innerWays = new ArrayList<>();
109        }
110    }
111
112    /** List of outer ways **/
113    public final List<JoinedPolygon> outerWays;
114    /** List of inner ways **/
115    public final List<JoinedPolygon> innerWays;
116
117    /**
118     * Constructs a new {@code MultipolygonBuilder} initialized with given ways.
119     * @param outerWays The outer ways
120     * @param innerWays The inner ways
121     */
122    public MultipolygonBuilder(List<JoinedPolygon> outerWays, List<JoinedPolygon> innerWays) {
123        this.outerWays = outerWays;
124        this.innerWays = innerWays;
125    }
126
127    /**
128     * Constructs a new empty {@code MultipolygonBuilder}.
129     */
130    public MultipolygonBuilder() {
131        this.outerWays = new ArrayList<>(0);
132        this.innerWays = new ArrayList<>(0);
133    }
134
135    /**
136     * Splits ways into inner and outer JoinedWays. Sets {@link #innerWays} and {@link #outerWays} to the result.
137     * TODO: Currently cannot process touching polygons. See code in JoinAreasAction.
138     * @param ways ways to analyze
139     * @return error description if the ways cannot be split, {@code null} if all fine.
140     */
141    public String makeFromWays(Collection<Way> ways) {
142        try {
143            List<JoinedPolygon> joinedWays = joinWays(ways);
144            //analyze witch way is inside witch outside.
145            return makeFromPolygons(joinedWays);
146        } catch (JoinedPolygonCreationException ex) {
147            Main.debug(ex);
148            return ex.getMessage();
149        }
150    }
151
152    /**
153     * An exception indicating an error while joining ways to multipolygon rings.
154     */
155    public static class JoinedPolygonCreationException extends RuntimeException {
156        /**
157         * Constructs a new {@code JoinedPolygonCreationException}.
158         * @param message the detail message. The detail message is saved for
159         *                later retrieval by the {@link #getMessage()} method
160         */
161        public JoinedPolygonCreationException(String message) {
162            super(message);
163        }
164    }
165
166    /**
167     * Joins the given {@code ways} to multipolygon rings.
168     * @param ways the ways to join.
169     * @return a list of multipolygon rings.
170     * @throws JoinedPolygonCreationException if the creation fails.
171     */
172    public static List<JoinedPolygon> joinWays(Collection<Way> ways) throws JoinedPolygonCreationException {
173        List<JoinedPolygon> joinedWays = new ArrayList<>();
174
175        //collect ways connecting to each node.
176        MultiMap<Node, Way> nodesWithConnectedWays = new MultiMap<>();
177        Set<Way> usedWays = new HashSet<>();
178
179        for (Way w: ways) {
180            if (w.getNodesCount() < 2) {
181                throw new JoinedPolygonCreationException(tr("Cannot add a way with only {0} nodes.", w.getNodesCount()));
182            }
183
184            if (w.isClosed()) {
185                //closed way, add as is.
186                JoinedPolygon jw = new JoinedPolygon(w);
187                joinedWays.add(jw);
188                usedWays.add(w);
189            } else {
190                nodesWithConnectedWays.put(w.lastNode(), w);
191                nodesWithConnectedWays.put(w.firstNode(), w);
192            }
193        }
194
195        //process unclosed ways
196        for (Way startWay: ways) {
197            if (usedWays.contains(startWay)) {
198                continue;
199            }
200
201            Node startNode = startWay.firstNode();
202            List<Way> collectedWays = new ArrayList<>();
203            List<Boolean> collectedWaysReverse = new ArrayList<>();
204            Way curWay = startWay;
205            Node prevNode = startNode;
206
207            //find polygon ways
208            while (true) {
209                boolean curWayReverse = prevNode == curWay.lastNode();
210                Node nextNode = curWayReverse ? curWay.firstNode() : curWay.lastNode();
211
212                //add cur way to the list
213                collectedWays.add(curWay);
214                collectedWaysReverse.add(Boolean.valueOf(curWayReverse));
215
216                if (nextNode == startNode) {
217                    //way finished
218                    break;
219                }
220
221                //find next way
222                Collection<Way> adjacentWays = nodesWithConnectedWays.get(nextNode);
223
224                if (adjacentWays.size() != 2) {
225                    throw new JoinedPolygonCreationException(tr("Each node must connect exactly 2 ways"));
226                }
227
228                Way nextWay = null;
229                for (Way way: adjacentWays) {
230                    if (way != curWay) {
231                        nextWay = way;
232                    }
233                }
234
235                //move to the next way
236                curWay = nextWay;
237                prevNode = nextNode;
238            }
239
240            usedWays.addAll(collectedWays);
241            joinedWays.add(new JoinedPolygon(collectedWays, collectedWaysReverse));
242        }
243
244        return joinedWays;
245    }
246
247    /**
248     * This method analyzes which ways are inner and which outer. Sets {@link #innerWays} and {@link #outerWays} to the result.
249     * @param polygons polygons to analyze
250     * @return error description if the ways cannot be split, {@code null} if all fine.
251     */
252    private String makeFromPolygons(List<JoinedPolygon> polygons) {
253        List<PolygonLevel> list = findOuterWaysMultiThread(polygons);
254
255        if (list == null) {
256            return tr("There is an intersection between ways.");
257        }
258
259        this.outerWays.clear();
260        this.innerWays.clear();
261
262        //take every other level
263        for (PolygonLevel pol : list) {
264            if (pol.level % 2 == 0) {
265                this.outerWays.add(pol.outerWay);
266            } else {
267                this.innerWays.add(pol.outerWay);
268            }
269        }
270
271        return null;
272    }
273
274    private static Pair<Boolean, List<JoinedPolygon>> findInnerWaysCandidates(JoinedPolygon outerWay, Collection<JoinedPolygon> boundaryWays) {
275        boolean outerGood = true;
276        List<JoinedPolygon> innerCandidates = new ArrayList<>();
277
278        for (JoinedPolygon innerWay : boundaryWays) {
279            if (innerWay == outerWay) {
280                continue;
281            }
282
283            // Preliminary computation on bounds. If bounds do not intersect, no need to do a costly area intersection
284            if (outerWay.bounds.intersects(innerWay.bounds)) {
285                // Bounds intersection, let's see in detail
286                PolygonIntersection intersection = Geometry.polygonIntersection(outerWay.area, innerWay.area);
287
288                if (intersection == PolygonIntersection.FIRST_INSIDE_SECOND) {
289                    outerGood = false;  // outer is inside another polygon
290                    break;
291                } else if (intersection == PolygonIntersection.SECOND_INSIDE_FIRST) {
292                    innerCandidates.add(innerWay);
293                } else if (intersection == PolygonIntersection.CROSSING) {
294                    // ways intersect
295                    return null;
296                }
297            }
298        }
299
300        return new Pair<>(outerGood, innerCandidates);
301    }
302
303    /**
304     * Collects outer way and corresponding inner ways from all boundaries.
305     * @param boundaryWays boundary ways
306     * @return the outermostWay, or {@code null} if intersection found.
307     */
308    private static List<PolygonLevel> findOuterWaysMultiThread(List<JoinedPolygon> boundaryWays) {
309        return THREAD_POOL.invoke(new Worker(boundaryWays, 0, boundaryWays.size(), new ArrayList<PolygonLevel>(),
310                Math.max(32, boundaryWays.size() / THREAD_POOL.getParallelism() / 3)));
311    }
312
313    private static class Worker extends RecursiveTask<List<PolygonLevel>> {
314
315        // Needed for Findbugs / Coverity because parent class is serializable
316        private static final long serialVersionUID = 1L;
317
318        private final transient List<JoinedPolygon> input;
319        private final int from;
320        private final int to;
321        private final transient List<PolygonLevel> output;
322        private final int directExecutionTaskSize;
323
324        Worker(List<JoinedPolygon> input, int from, int to, List<PolygonLevel> output, int directExecutionTaskSize) {
325            this.input = input;
326            this.from = from;
327            this.to = to;
328            this.output = output;
329            this.directExecutionTaskSize = directExecutionTaskSize;
330        }
331
332        /**
333         * Collects outer way and corresponding inner ways from all boundaries.
334         * @param level nesting level
335         * @param boundaryWays boundary ways
336         * @return the outermostWay, or {@code null} if intersection found.
337         */
338        private static List<PolygonLevel> findOuterWaysRecursive(int level, List<JoinedPolygon> boundaryWays) {
339
340            final List<PolygonLevel> result = new ArrayList<>();
341
342            for (JoinedPolygon outerWay : boundaryWays) {
343                if (processOuterWay(level, boundaryWays, result, outerWay) == null) {
344                    return null;
345                }
346            }
347
348            return result;
349        }
350
351        private static List<PolygonLevel> processOuterWay(int level, List<JoinedPolygon> boundaryWays,
352                final List<PolygonLevel> result, JoinedPolygon outerWay) {
353            Pair<Boolean, List<JoinedPolygon>> p = findInnerWaysCandidates(outerWay, boundaryWays);
354            if (p == null) {
355                // ways intersect
356                return null;
357            }
358
359            if (p.a) {
360                //add new outer polygon
361                PolygonLevel pol = new PolygonLevel(outerWay, level);
362
363                //process inner ways
364                if (!p.b.isEmpty()) {
365                    List<PolygonLevel> innerList = findOuterWaysRecursive(level + 1, p.b);
366                    if (innerList == null) {
367                        return null; //intersection found
368                    }
369
370                    result.addAll(innerList);
371
372                    for (PolygonLevel pl : innerList) {
373                        if (pl.level == level + 1) {
374                            pol.innerWays.add(pl.outerWay);
375                        }
376                    }
377                }
378
379                result.add(pol);
380            }
381            return result;
382        }
383
384        @Override
385        protected List<PolygonLevel> compute() {
386            if (to - from <= directExecutionTaskSize) {
387                return computeDirectly();
388            } else {
389                final Collection<ForkJoinTask<List<PolygonLevel>>> tasks = new ArrayList<>();
390                for (int fromIndex = from; fromIndex < to; fromIndex += directExecutionTaskSize) {
391                    tasks.add(new Worker(input, fromIndex, Math.min(fromIndex + directExecutionTaskSize, to),
392                            new ArrayList<PolygonLevel>(), directExecutionTaskSize));
393                }
394                for (ForkJoinTask<List<PolygonLevel>> task : ForkJoinTask.invokeAll(tasks)) {
395                    List<PolygonLevel> res = task.join();
396                    if (res == null) {
397                        return null;
398                    }
399                    output.addAll(res);
400                }
401                return output;
402            }
403        }
404
405        List<PolygonLevel> computeDirectly() {
406            for (int i = from; i < to; i++) {
407                if (processOuterWay(0, input, output, input.get(i)) == null) {
408                    return null;
409                }
410            }
411            return output;
412        }
413
414        private void readObject(ObjectInputStream ois) throws ClassNotFoundException, IOException {
415            // Needed for Findbugs / Coverity because parent class is serializable
416            ois.defaultReadObject();
417        }
418
419        private void writeObject(ObjectOutputStream oos) throws IOException {
420            // Needed for Findbugs / Coverity because parent class is serializable
421            oos.defaultWriteObject();
422        }
423    }
424}