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