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 if (!mpTest.getErrors().isEmpty()) { 121 return mpTest.getErrors().iterator().next().getMessage(); 122 } 123 Pair<List<JoinedPolygon>, List<JoinedPolygon>> outerInner = joinWays(calculated); 124 this.outerWays.clear(); 125 this.innerWays.clear(); 126 this.outerWays.addAll(outerInner.a); 127 this.innerWays.addAll(outerInner.b); 128 return null; 129 } 130 131 /** 132 * An exception indicating an error while joining ways to multipolygon rings. 133 */ 134 public static class JoinedPolygonCreationException extends RuntimeException { 135 /** 136 * Constructs a new {@code JoinedPolygonCreationException}. 137 * @param message the detail message. The detail message is saved for 138 * later retrieval by the {@link #getMessage()} method 139 */ 140 public JoinedPolygonCreationException(String message) { 141 super(message); 142 } 143 } 144 145 /** 146 * Joins the given {@code multipolygon} to a pair of outer and inner multipolygon rings. 147 * 148 * @param multipolygon the multipolygon to join. 149 * @return a pair of outer and inner multipolygon rings. 150 * @throws JoinedPolygonCreationException if the creation fails. 151 */ 152 public static Pair<List<JoinedPolygon>, List<JoinedPolygon>> joinWays(Relation multipolygon) { 153 CheckParameterUtil.ensureThat(multipolygon.isMultipolygon(), "multipolygon.isMultipolygon"); 154 final Map<String, Set<Way>> members = multipolygon.getMembers().stream() 155 .filter(RelationMember::isWay) 156 .collect(Collectors.groupingBy(RelationMember::getRole, Collectors.mapping(RelationMember::getWay, Collectors.toSet()))); 157 final List<JoinedPolygon> outerRings = joinWays(members.getOrDefault("outer", Collections.emptySet())); 158 final List<JoinedPolygon> innerRings = joinWays(members.getOrDefault("inner", Collections.emptySet())); 159 return Pair.create(outerRings, innerRings); 160 } 161 162 /** 163 * Joins the given {@code ways} to multipolygon rings. 164 * @param ways the ways to join. 165 * @return a list of multipolygon rings. 166 * @throws JoinedPolygonCreationException if the creation fails. 167 */ 168 public static List<JoinedPolygon> joinWays(Collection<Way> ways) { 169 List<JoinedPolygon> joinedWays = new ArrayList<>(); 170 171 //collect ways connecting to each node. 172 MultiMap<Node, Way> nodesWithConnectedWays = new MultiMap<>(); 173 Set<Way> usedWays = new HashSet<>(); 174 175 for (Way w: ways) { 176 if (w.getNodesCount() < 2) { 177 throw new JoinedPolygonCreationException(tr("Cannot add a way with only {0} nodes.", w.getNodesCount())); 178 } 179 180 if (w.isClosed()) { 181 //closed way, add as is. 182 JoinedPolygon jw = new JoinedPolygon(w); 183 joinedWays.add(jw); 184 usedWays.add(w); 185 } else { 186 nodesWithConnectedWays.put(w.lastNode(), w); 187 nodesWithConnectedWays.put(w.firstNode(), w); 188 } 189 } 190 191 //process unclosed ways 192 for (Way startWay: ways) { 193 if (usedWays.contains(startWay)) { 194 continue; 195 } 196 197 Node startNode = startWay.firstNode(); 198 List<Way> collectedWays = new ArrayList<>(); 199 List<Boolean> collectedWaysReverse = new ArrayList<>(); 200 Way curWay = startWay; 201 Node prevNode = startNode; 202 203 //find polygon ways 204 while (true) { 205 boolean curWayReverse = prevNode == curWay.lastNode(); 206 Node nextNode = curWayReverse ? curWay.firstNode() : curWay.lastNode(); 207 208 //add cur way to the list 209 collectedWays.add(curWay); 210 collectedWaysReverse.add(Boolean.valueOf(curWayReverse)); 211 212 if (nextNode == startNode) { 213 //way finished 214 break; 215 } 216 217 //find next way 218 Collection<Way> adjacentWays = nodesWithConnectedWays.get(nextNode); 219 220 if (adjacentWays.size() != 2) { 221 throw new JoinedPolygonCreationException(tr("Each node must connect exactly 2 ways")); 222 } 223 224 Way nextWay = null; 225 for (Way way: adjacentWays) { 226 if (way != curWay) { 227 nextWay = way; 228 } 229 } 230 231 //move to the next way 232 curWay = nextWay; 233 prevNode = nextNode; 234 } 235 236 usedWays.addAll(collectedWays); 237 joinedWays.add(new JoinedPolygon(collectedWays, collectedWaysReverse)); 238 } 239 240 return joinedWays; 241 } 242}