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.Map;
014import java.util.Set;
015import java.util.stream.Collectors;
016
017import org.openstreetmap.josm.data.validation.tests.MultipolygonTest;
018import org.openstreetmap.josm.tools.CheckParameterUtil;
019import org.openstreetmap.josm.tools.Geometry;
020import org.openstreetmap.josm.tools.MultiMap;
021import org.openstreetmap.josm.tools.Pair;
022
023/**
024 * Helper class to build multipolygons from multiple ways.
025 * @author viesturs
026 * @since 7392 (rename)
027 * @since 3704
028 */
029public class MultipolygonBuilder {
030
031    /**
032     * Represents one polygon that consists of multiple ways.
033     */
034    public static class JoinedPolygon {
035        /** list of ways building this polygon */
036        public final List<Way> ways;
037        /** list of flags that indicate if the nodes of the way in the same position where reversed */
038        public final List<Boolean> reversed;
039        /** the nodes of the polygon, first node is not duplicated as last node. */
040        public final List<Node> nodes;
041        /** the area in east/north space */
042        public final Area area;
043        /** the integer bounds,
044         * @deprecated better use area.getBounds2D()
045         *  */
046        @Deprecated
047        public final Rectangle bounds;
048
049        /**
050         * Constructs a new {@code JoinedPolygon} from given list of ways.
051         * @param ways The ways used to build joined polygon
052         * @param reversed list of reversed states
053         */
054        public JoinedPolygon(List<Way> ways, List<Boolean> reversed) {
055            this.ways = ways;
056            this.reversed = reversed;
057            this.nodes = this.getNodes();
058            this.area = Geometry.getArea(nodes);
059            this.bounds = area.getBounds();
060        }
061
062        /**
063         * Creates a polygon from single way.
064         * @param way the way to form the polygon
065         */
066        public JoinedPolygon(Way way) {
067            this(Collections.singletonList(way), Collections.singletonList(Boolean.FALSE));
068        }
069
070        /**
071         * Builds a list of nodes for this polygon. First node is not duplicated as last node.
072         * @return list of nodes
073         */
074        public List<Node> getNodes() {
075            List<Node> ringNodes = new ArrayList<>();
076
077            for (int waypos = 0; waypos < this.ways.size(); waypos++) {
078                Way way = this.ways.get(waypos);
079
080                if (!this.reversed.get(waypos)) {
081                    for (int pos = 0; pos < way.getNodesCount() - 1; pos++) {
082                        ringNodes.add(way.getNode(pos));
083                    }
084                } else {
085                    for (int pos = way.getNodesCount() - 1; pos > 0; pos--) {
086                        ringNodes.add(way.getNode(pos));
087                    }
088                }
089            }
090
091            return ringNodes;
092        }
093    }
094
095    /** List of outer ways **/
096    public final List<JoinedPolygon> outerWays;
097    /** List of inner ways **/
098    public final List<JoinedPolygon> innerWays;
099
100    /**
101     * Constructs a new {@code MultipolygonBuilder} initialized with given ways.
102     * @param outerWays The outer ways
103     * @param innerWays The inner ways
104     */
105    public MultipolygonBuilder(List<JoinedPolygon> outerWays, List<JoinedPolygon> innerWays) {
106        this.outerWays = outerWays;
107        this.innerWays = innerWays;
108    }
109
110    /**
111     * Constructs a new empty {@code MultipolygonBuilder}.
112     */
113    public MultipolygonBuilder() {
114        this.outerWays = new ArrayList<>(0);
115        this.innerWays = new ArrayList<>(0);
116    }
117
118    /**
119     * Splits ways into inner and outer JoinedWays. Sets {@link #innerWays} and {@link #outerWays} to the result.
120     * Calculation is done in {@link MultipolygonTest#makeFromWays(Collection)} to ensure that the result is a valid multipolygon.
121     * @param ways ways to analyze
122     * @return error description if the ways cannot be split, {@code null} if all fine.
123     */
124    public String makeFromWays(Collection<Way> ways) {
125        MultipolygonTest mpTest = new MultipolygonTest();
126        Relation calculated = mpTest.makeFromWays(ways);
127        if (!mpTest.getErrors().isEmpty()) {
128            return mpTest.getErrors().iterator().next().getMessage();
129        }
130        Pair<List<JoinedPolygon>, List<JoinedPolygon>> outerInner = joinWays(calculated);
131        this.outerWays.clear();
132        this.innerWays.clear();
133        this.outerWays.addAll(outerInner.a);
134        this.innerWays.addAll(outerInner.b);
135        return null;
136    }
137
138    /**
139     * An exception indicating an error while joining ways to multipolygon rings.
140     */
141    public static class JoinedPolygonCreationException extends RuntimeException {
142        /**
143         * Constructs a new {@code JoinedPolygonCreationException}.
144         * @param message the detail message. The detail message is saved for
145         *                later retrieval by the {@link #getMessage()} method
146         */
147        public JoinedPolygonCreationException(String message) {
148            super(message);
149        }
150    }
151
152    /**
153     * Joins the given {@code multipolygon} to a pair of outer and inner multipolygon rings.
154     *
155     * @param multipolygon the multipolygon to join.
156     * @return a pair of outer and inner multipolygon rings.
157     * @throws JoinedPolygonCreationException if the creation fails.
158     */
159    public static Pair<List<JoinedPolygon>, List<JoinedPolygon>> joinWays(Relation multipolygon) {
160        CheckParameterUtil.ensureThat(multipolygon.isMultipolygon(), "multipolygon.isMultipolygon");
161        final Map<String, Set<Way>> members = multipolygon.getMembers().stream()
162                .filter(RelationMember::isWay)
163                .collect(Collectors.groupingBy(RelationMember::getRole, Collectors.mapping(RelationMember::getWay, Collectors.toSet())));
164        final List<JoinedPolygon> outerRings = joinWays(members.getOrDefault("outer", Collections.emptySet()));
165        final List<JoinedPolygon> innerRings = joinWays(members.getOrDefault("inner", Collections.emptySet()));
166        return Pair.create(outerRings, innerRings);
167    }
168
169    /**
170     * Joins the given {@code ways} to multipolygon rings.
171     * @param ways the ways to join.
172     * @return a list of multipolygon rings.
173     * @throws JoinedPolygonCreationException if the creation fails.
174     */
175    public static List<JoinedPolygon> joinWays(Collection<Way> ways) {
176        List<JoinedPolygon> joinedWays = new ArrayList<>();
177
178        //collect ways connecting to each node.
179        MultiMap<Node, Way> nodesWithConnectedWays = new MultiMap<>();
180        Set<Way> usedWays = new HashSet<>();
181
182        for (Way w: ways) {
183            if (w.getNodesCount() < 2) {
184                throw new JoinedPolygonCreationException(tr("Cannot add a way with only {0} nodes.", w.getNodesCount()));
185            }
186
187            if (w.isClosed()) {
188                //closed way, add as is.
189                JoinedPolygon jw = new JoinedPolygon(w);
190                joinedWays.add(jw);
191                usedWays.add(w);
192            } else {
193                nodesWithConnectedWays.put(w.lastNode(), w);
194                nodesWithConnectedWays.put(w.firstNode(), w);
195            }
196        }
197
198        //process unclosed ways
199        for (Way startWay: ways) {
200            if (usedWays.contains(startWay)) {
201                continue;
202            }
203
204            Node startNode = startWay.firstNode();
205            List<Way> collectedWays = new ArrayList<>();
206            List<Boolean> collectedWaysReverse = new ArrayList<>();
207            Way curWay = startWay;
208            Node prevNode = startNode;
209
210            //find polygon ways
211            while (true) {
212                boolean curWayReverse = prevNode == curWay.lastNode();
213                Node nextNode = curWayReverse ? curWay.firstNode() : curWay.lastNode();
214
215                //add cur way to the list
216                collectedWays.add(curWay);
217                collectedWaysReverse.add(Boolean.valueOf(curWayReverse));
218
219                if (nextNode == startNode) {
220                    //way finished
221                    break;
222                }
223
224                //find next way
225                Collection<Way> adjacentWays = nodesWithConnectedWays.get(nextNode);
226
227                if (adjacentWays.size() != 2) {
228                    throw new JoinedPolygonCreationException(tr("Each node must connect exactly 2 ways"));
229                }
230
231                Way nextWay = null;
232                for (Way way: adjacentWays) {
233                    if (way != curWay) {
234                        nextWay = way;
235                    }
236                }
237
238                //move to the next way
239                curWay = nextWay;
240                prevNode = nextNode;
241            }
242
243            usedWays.addAll(collectedWays);
244            joinedWays.add(new JoinedPolygon(collectedWays, collectedWaysReverse));
245        }
246
247        return joinedWays;
248    }
249}