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