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}