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