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}