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