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