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.io.IOException; 009import java.io.ObjectInputStream; 010import java.io.ObjectOutputStream; 011import java.util.ArrayList; 012import java.util.Collection; 013import java.util.Collections; 014import java.util.HashSet; 015import java.util.List; 016import java.util.Set; 017import java.util.concurrent.ForkJoinPool; 018import java.util.concurrent.ForkJoinTask; 019import java.util.concurrent.RecursiveTask; 020 021import org.openstreetmap.josm.tools.Geometry; 022import org.openstreetmap.josm.tools.Geometry.PolygonIntersection; 023import org.openstreetmap.josm.tools.MultiMap; 024import org.openstreetmap.josm.tools.Pair; 025import org.openstreetmap.josm.tools.Utils; 026 027/** 028 * Helper class to build multipolygons from multiple ways. 029 * @author viesturs 030 * @since 7392 (rename) 031 * @since 3704 032 */ 033public class MultipolygonBuilder { 034 035 private static final ForkJoinPool THREAD_POOL = 036 Utils.newForkJoinPool("multipolygon_creation.numberOfThreads", "multipolygon-builder-%d", Thread.NORM_PRIORITY); 037 038 /** 039 * Represents one polygon that consists of multiple ways. 040 */ 041 public static class JoinedPolygon { 042 public final List<Way> ways; 043 public final List<Boolean> reversed; 044 public final List<Node> nodes; 045 public final Area area; 046 public final Rectangle bounds; 047 048 /** 049 * Constructs a new {@code JoinedPolygon} from given list of ways. 050 * @param ways The ways used to build joined polygon 051 * @param reversed list of reversed states 052 */ 053 public JoinedPolygon(List<Way> ways, List<Boolean> reversed) { 054 this.ways = ways; 055 this.reversed = reversed; 056 this.nodes = this.getNodes(); 057 this.area = Geometry.getArea(nodes); 058 this.bounds = area.getBounds(); 059 } 060 061 /** 062 * Creates a polygon from single way. 063 * @param way the way to form the polygon 064 */ 065 public JoinedPolygon(Way way) { 066 this(Collections.singletonList(way), Collections.singletonList(Boolean.FALSE)); 067 } 068 069 /** 070 * Builds a list of nodes for this polygon. First node is not duplicated as last node. 071 * @return list of nodes 072 */ 073 public List<Node> getNodes() { 074 List<Node> nodes = new ArrayList<>(); 075 076 for (int waypos = 0; waypos < this.ways.size(); waypos++) { 077 Way way = this.ways.get(waypos); 078 boolean reversed = this.reversed.get(waypos).booleanValue(); 079 080 if (!reversed) { 081 for (int pos = 0; pos < way.getNodesCount() - 1; pos++) { 082 nodes.add(way.getNode(pos)); 083 } 084 } else { 085 for (int pos = way.getNodesCount() - 1; pos > 0; pos--) { 086 nodes.add(way.getNode(pos)); 087 } 088 } 089 } 090 091 return nodes; 092 } 093 } 094 095 /** 096 * Helper storage class for finding findOuterWays 097 */ 098 static class PolygonLevel { 099 public final int level; // nesting level, even for outer, odd for inner polygons. 100 public final JoinedPolygon outerWay; 101 102 public List<JoinedPolygon> innerWays; 103 104 PolygonLevel(JoinedPolygon pol, int level) { 105 this.outerWay = pol; 106 this.level = level; 107 this.innerWays = new ArrayList<>(); 108 } 109 } 110 111 /** List of outer ways **/ 112 public final List<JoinedPolygon> outerWays; 113 /** List of inner ways **/ 114 public final List<JoinedPolygon> innerWays; 115 116 /** 117 * Constructs a new {@code MultipolygonBuilder} initialized with given ways. 118 * @param outerWays The outer ways 119 * @param innerWays The inner ways 120 */ 121 public MultipolygonBuilder(List<JoinedPolygon> outerWays, List<JoinedPolygon> innerWays) { 122 this.outerWays = outerWays; 123 this.innerWays = innerWays; 124 } 125 126 /** 127 * Constructs a new empty {@code MultipolygonBuilder}. 128 */ 129 public MultipolygonBuilder() { 130 this.outerWays = new ArrayList<>(0); 131 this.innerWays = new ArrayList<>(0); 132 } 133 134 /** 135 * Splits ways into inner and outer JoinedWays. Sets {@link #innerWays} and {@link #outerWays} to the result. 136 * TODO: Currently cannot process touching polygons. See code in JoinAreasAction. 137 * @param ways ways to analyze 138 * @return error description if the ways cannot be split, {@code null} if all fine. 139 */ 140 public String makeFromWays(Collection<Way> ways) { 141 try { 142 List<JoinedPolygon> joinedWays = joinWays(ways); 143 //analyze witch way is inside witch outside. 144 return makeFromPolygons(joinedWays); 145 } catch (JoinedPolygonCreationException ex) { 146 return ex.getMessage(); 147 } 148 } 149 150 /** 151 * An exception indicating an error while joining ways to multipolygon rings. 152 */ 153 public static class JoinedPolygonCreationException extends RuntimeException { 154 /** 155 * Constructs a new {@code JoinedPolygonCreationException}. 156 * @param message the detail message. The detail message is saved for 157 * later retrieval by the {@link #getMessage()} method 158 */ 159 public JoinedPolygonCreationException(String message) { 160 super(message); 161 } 162 } 163 164 /** 165 * Joins the given {@code ways} to multipolygon rings. 166 * @param ways the ways to join. 167 * @return a list of multipolygon rings. 168 * @throws JoinedPolygonCreationException if the creation fails. 169 */ 170 public static List<JoinedPolygon> joinWays(Collection<Way> ways) throws JoinedPolygonCreationException { 171 List<JoinedPolygon> joinedWays = new ArrayList<>(); 172 173 //collect ways connecting to each node. 174 MultiMap<Node, Way> nodesWithConnectedWays = new MultiMap<>(); 175 Set<Way> usedWays = new HashSet<>(); 176 177 for (Way w: ways) { 178 if (w.getNodesCount() < 2) { 179 throw new JoinedPolygonCreationException(tr("Cannot add a way with only {0} nodes.", w.getNodesCount())); 180 } 181 182 if (w.isClosed()) { 183 //closed way, add as is. 184 JoinedPolygon jw = new JoinedPolygon(w); 185 joinedWays.add(jw); 186 usedWays.add(w); 187 } else { 188 nodesWithConnectedWays.put(w.lastNode(), w); 189 nodesWithConnectedWays.put(w.firstNode(), w); 190 } 191 } 192 193 //process unclosed ways 194 for (Way startWay: ways) { 195 if (usedWays.contains(startWay)) { 196 continue; 197 } 198 199 Node startNode = startWay.firstNode(); 200 List<Way> collectedWays = new ArrayList<>(); 201 List<Boolean> collectedWaysReverse = new ArrayList<>(); 202 Way curWay = startWay; 203 Node prevNode = startNode; 204 205 //find polygon ways 206 while (true) { 207 boolean curWayReverse = prevNode == curWay.lastNode(); 208 Node nextNode = curWayReverse ? curWay.firstNode() : curWay.lastNode(); 209 210 //add cur way to the list 211 collectedWays.add(curWay); 212 collectedWaysReverse.add(Boolean.valueOf(curWayReverse)); 213 214 if (nextNode == startNode) { 215 //way finished 216 break; 217 } 218 219 //find next way 220 Collection<Way> adjacentWays = nodesWithConnectedWays.get(nextNode); 221 222 if (adjacentWays.size() != 2) { 223 throw new JoinedPolygonCreationException(tr("Each node must connect exactly 2 ways")); 224 } 225 226 Way nextWay = null; 227 for (Way way: adjacentWays) { 228 if (way != curWay) { 229 nextWay = way; 230 } 231 } 232 233 //move to the next way 234 curWay = nextWay; 235 prevNode = nextNode; 236 } 237 238 usedWays.addAll(collectedWays); 239 joinedWays.add(new JoinedPolygon(collectedWays, collectedWaysReverse)); 240 } 241 242 return joinedWays; 243 } 244 245 /** 246 * This method analyzes which ways are inner and which outer. Sets {@link #innerWays} and {@link #outerWays} to the result. 247 * @param polygons polygons to analyze 248 * @return error description if the ways cannot be split, {@code null} if all fine. 249 */ 250 private String makeFromPolygons(List<JoinedPolygon> polygons) { 251 List<PolygonLevel> list = findOuterWaysMultiThread(polygons); 252 253 if (list == null) { 254 return tr("There is an intersection between ways."); 255 } 256 257 this.outerWays.clear(); 258 this.innerWays.clear(); 259 260 //take every other level 261 for (PolygonLevel pol : list) { 262 if (pol.level % 2 == 0) { 263 this.outerWays.add(pol.outerWay); 264 } else { 265 this.innerWays.add(pol.outerWay); 266 } 267 } 268 269 return null; 270 } 271 272 private static Pair<Boolean, List<JoinedPolygon>> findInnerWaysCandidates(JoinedPolygon outerWay, Collection<JoinedPolygon> boundaryWays) { 273 boolean outerGood = true; 274 List<JoinedPolygon> innerCandidates = new ArrayList<>(); 275 276 for (JoinedPolygon innerWay : boundaryWays) { 277 if (innerWay == outerWay) { 278 continue; 279 } 280 281 // Preliminary computation on bounds. If bounds do not intersect, no need to do a costly area intersection 282 if (outerWay.bounds.intersects(innerWay.bounds)) { 283 // Bounds intersection, let's see in detail 284 PolygonIntersection intersection = Geometry.polygonIntersection(outerWay.area, innerWay.area); 285 286 if (intersection == PolygonIntersection.FIRST_INSIDE_SECOND) { 287 outerGood = false; // outer is inside another polygon 288 break; 289 } else if (intersection == PolygonIntersection.SECOND_INSIDE_FIRST) { 290 innerCandidates.add(innerWay); 291 } else if (intersection == PolygonIntersection.CROSSING) { 292 // ways intersect 293 return null; 294 } 295 } 296 } 297 298 return new Pair<>(outerGood, innerCandidates); 299 } 300 301 /** 302 * Collects outer way and corresponding inner ways from all boundaries. 303 * @param boundaryWays boundary ways 304 * @return the outermostWay, or {@code null} if intersection found. 305 */ 306 private static List<PolygonLevel> findOuterWaysMultiThread(List<JoinedPolygon> boundaryWays) { 307 return THREAD_POOL.invoke(new Worker(boundaryWays, 0, boundaryWays.size(), new ArrayList<PolygonLevel>(), 308 Math.max(32, boundaryWays.size() / THREAD_POOL.getParallelism() / 3))); 309 } 310 311 private static class Worker extends RecursiveTask<List<PolygonLevel>> { 312 313 // Needed for Findbugs / Coverity because parent class is serializable 314 private static final long serialVersionUID = 1L; 315 316 private final transient List<JoinedPolygon> input; 317 private final int from; 318 private final int to; 319 private final transient List<PolygonLevel> output; 320 private final int directExecutionTaskSize; 321 322 Worker(List<JoinedPolygon> input, int from, int to, List<PolygonLevel> output, int directExecutionTaskSize) { 323 this.input = input; 324 this.from = from; 325 this.to = to; 326 this.output = output; 327 this.directExecutionTaskSize = directExecutionTaskSize; 328 } 329 330 /** 331 * Collects outer way and corresponding inner ways from all boundaries. 332 * @param level nesting level 333 * @param boundaryWays boundary ways 334 * @return the outermostWay, or {@code null} if intersection found. 335 */ 336 private static List<PolygonLevel> findOuterWaysRecursive(int level, List<JoinedPolygon> boundaryWays) { 337 338 final List<PolygonLevel> result = new ArrayList<>(); 339 340 for (JoinedPolygon outerWay : boundaryWays) { 341 if (processOuterWay(level, boundaryWays, result, outerWay) == null) { 342 return null; 343 } 344 } 345 346 return result; 347 } 348 349 private static List<PolygonLevel> processOuterWay(int level, List<JoinedPolygon> boundaryWays, 350 final List<PolygonLevel> result, JoinedPolygon outerWay) { 351 Pair<Boolean, List<JoinedPolygon>> p = findInnerWaysCandidates(outerWay, boundaryWays); 352 if (p == null) { 353 // ways intersect 354 return null; 355 } 356 357 if (p.a) { 358 //add new outer polygon 359 PolygonLevel pol = new PolygonLevel(outerWay, level); 360 361 //process inner ways 362 if (!p.b.isEmpty()) { 363 List<PolygonLevel> innerList = findOuterWaysRecursive(level + 1, p.b); 364 if (innerList == null) { 365 return null; //intersection found 366 } 367 368 result.addAll(innerList); 369 370 for (PolygonLevel pl : innerList) { 371 if (pl.level == level + 1) { 372 pol.innerWays.add(pl.outerWay); 373 } 374 } 375 } 376 377 result.add(pol); 378 } 379 return result; 380 } 381 382 @Override 383 protected List<PolygonLevel> compute() { 384 if (to - from <= directExecutionTaskSize) { 385 return computeDirectly(); 386 } else { 387 final Collection<ForkJoinTask<List<PolygonLevel>>> tasks = new ArrayList<>(); 388 for (int fromIndex = from; fromIndex < to; fromIndex += directExecutionTaskSize) { 389 tasks.add(new Worker(input, fromIndex, Math.min(fromIndex + directExecutionTaskSize, to), 390 new ArrayList<PolygonLevel>(), directExecutionTaskSize)); 391 } 392 for (ForkJoinTask<List<PolygonLevel>> task : ForkJoinTask.invokeAll(tasks)) { 393 List<PolygonLevel> res = task.join(); 394 if (res == null) { 395 return null; 396 } 397 output.addAll(res); 398 } 399 return output; 400 } 401 } 402 403 List<PolygonLevel> computeDirectly() { 404 for (int i = from; i < to; i++) { 405 if (processOuterWay(0, input, output, input.get(i)) == null) { 406 return null; 407 } 408 } 409 return output; 410 } 411 412 private void readObject(ObjectInputStream ois) throws ClassNotFoundException, IOException { 413 // Needed for Findbugs / Coverity because parent class is serializable 414 ois.defaultReadObject(); 415 } 416 417 private void writeObject(ObjectOutputStream oos) throws IOException { 418 // Needed for Findbugs / Coverity because parent class is serializable 419 oos.defaultWriteObject(); 420 } 421 } 422}