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