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.Set; 014import java.util.concurrent.Callable; 015import java.util.concurrent.ExecutionException; 016import java.util.concurrent.ExecutorService; 017import java.util.concurrent.Future; 018 019import org.openstreetmap.josm.tools.Geometry; 020import org.openstreetmap.josm.tools.Geometry.PolygonIntersection; 021import org.openstreetmap.josm.tools.MultiMap; 022import org.openstreetmap.josm.tools.Pair; 023import org.openstreetmap.josm.tools.Utils; 024 025/** 026 * Helper class to build multipolygons from multiple ways. 027 * @author viesturs 028 * @since 7392 (rename) 029 * @since 3704 030 */ 031public class MultipolygonBuilder { 032 033 private static final Pair<Integer, ExecutorService> THREAD_POOL = 034 Utils.newThreadPool("multipolygon_creation.numberOfThreads", "multipolygon-builder-%d", Thread.NORM_PRIORITY); 035 036 /** 037 * Represents one polygon that consists of multiple ways. 038 */ 039 public static class JoinedPolygon { 040 public final List<Way> ways; 041 public final List<Boolean> reversed; 042 public final List<Node> nodes; 043 public final Area area; 044 public final Rectangle bounds; 045 046 /** 047 * Constructs a new {@code JoinedPolygon} from given list of ways. 048 * @param ways The ways used to build joined polygon 049 * @param reversed list of reversed states 050 */ 051 public JoinedPolygon(List<Way> ways, List<Boolean> reversed) { 052 this.ways = ways; 053 this.reversed = reversed; 054 this.nodes = this.getNodes(); 055 this.area = Geometry.getArea(nodes); 056 this.bounds = area.getBounds(); 057 } 058 059 /** 060 * Creates a polygon from single way. 061 * @param way the way to form the polygon 062 */ 063 public JoinedPolygon(Way way) { 064 this(Collections.singletonList(way), Collections.singletonList(Boolean.FALSE)); 065 } 066 067 /** 068 * Builds a list of nodes for this polygon. First node is not duplicated as last node. 069 * @return list of nodes 070 */ 071 public List<Node> getNodes() { 072 List<Node> nodes = new ArrayList<>(); 073 074 for (int waypos = 0; waypos < this.ways.size(); waypos++) { 075 Way way = this.ways.get(waypos); 076 boolean reversed = this.reversed.get(waypos).booleanValue(); 077 078 if (!reversed) { 079 for (int pos = 0; pos < way.getNodesCount() - 1; pos++) { 080 nodes.add(way.getNode(pos)); 081 } 082 } else { 083 for (int pos = way.getNodesCount() - 1; pos > 0; pos--) { 084 nodes.add(way.getNode(pos)); 085 } 086 } 087 } 088 089 return nodes; 090 } 091 } 092 093 /** 094 * Helper storage class for finding findOuterWays 095 */ 096 static class PolygonLevel { 097 public final int level; // nesting level, even for outer, odd for inner polygons. 098 public final JoinedPolygon outerWay; 099 100 public List<JoinedPolygon> innerWays; 101 102 PolygonLevel(JoinedPolygon pol, int level) { 103 this.outerWay = pol; 104 this.level = level; 105 this.innerWays = new ArrayList<>(); 106 } 107 } 108 109 /** List of outer ways **/ 110 public final List<JoinedPolygon> outerWays; 111 /** List of inner ways **/ 112 public final List<JoinedPolygon> innerWays; 113 114 /** 115 * Constructs a new {@code MultipolygonBuilder} initialized with given ways. 116 * @param outerWays The outer ways 117 * @param innerWays The inner ways 118 */ 119 public MultipolygonBuilder(List<JoinedPolygon> outerWays, List<JoinedPolygon> innerWays) { 120 this.outerWays = outerWays; 121 this.innerWays = innerWays; 122 } 123 124 /** 125 * Constructs a new empty {@code MultipolygonBuilder}. 126 */ 127 public MultipolygonBuilder() { 128 this.outerWays = new ArrayList<>(0); 129 this.innerWays = new ArrayList<>(0); 130 } 131 132 /** 133 * Splits ways into inner and outer JoinedWays. Sets {@link #innerWays} and {@link #outerWays} to the result. 134 * TODO: Currently cannot process touching polygons. See code in JoinAreasAction. 135 * @param ways ways to analyze 136 * @return error description if the ways cannot be split, {@code null} if all fine. 137 */ 138 public String makeFromWays(Collection<Way> ways) { 139 try { 140 List<JoinedPolygon> joinedWays = joinWays(ways); 141 //analyze witch way is inside witch outside. 142 return makeFromPolygons(joinedWays); 143 } catch (JoinedPolygonCreationException ex) { 144 return ex.getMessage(); 145 } 146 } 147 148 /** 149 * An exception indicating an error while joining ways to multipolygon rings. 150 */ 151 public static class JoinedPolygonCreationException extends RuntimeException { 152 /** 153 * Constructs a new {@code JoinedPolygonCreationException}. 154 * @param message the detail message. The detail message is saved for 155 * later retrieval by the {@link #getMessage()} method 156 */ 157 public JoinedPolygonCreationException(String message) { 158 super(message); 159 } 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) throws JoinedPolygonCreationException { 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 243 /** 244 * This method analyzes which ways are inner and which outer. Sets {@link #innerWays} and {@link #outerWays} to the result. 245 * @param polygons polygons to analyze 246 * @return error description if the ways cannot be split, {@code null} if all fine. 247 */ 248 private String makeFromPolygons(List<JoinedPolygon> polygons) { 249 List<PolygonLevel> list = findOuterWaysMultiThread(polygons); 250 251 if (list == null) { 252 return tr("There is an intersection between ways."); 253 } 254 255 this.outerWays.clear(); 256 this.innerWays.clear(); 257 258 //take every other level 259 for (PolygonLevel pol : list) { 260 if (pol.level % 2 == 0) { 261 this.outerWays.add(pol.outerWay); 262 } else { 263 this.innerWays.add(pol.outerWay); 264 } 265 } 266 267 return null; 268 } 269 270 private static Pair<Boolean, List<JoinedPolygon>> findInnerWaysCandidates(JoinedPolygon outerWay, Collection<JoinedPolygon> boundaryWays) { 271 boolean outerGood = true; 272 List<JoinedPolygon> innerCandidates = new ArrayList<>(); 273 274 for (JoinedPolygon innerWay : boundaryWays) { 275 if (innerWay == outerWay) { 276 continue; 277 } 278 279 // Preliminary computation on bounds. If bounds do not intersect, no need to do a costly area intersection 280 if (outerWay.bounds.intersects(innerWay.bounds)) { 281 // Bounds intersection, let's see in detail 282 PolygonIntersection intersection = Geometry.polygonIntersection(outerWay.area, innerWay.area); 283 284 if (intersection == PolygonIntersection.FIRST_INSIDE_SECOND) { 285 outerGood = false; // outer is inside another polygon 286 break; 287 } else if (intersection == PolygonIntersection.SECOND_INSIDE_FIRST) { 288 innerCandidates.add(innerWay); 289 } else if (intersection == PolygonIntersection.CROSSING) { 290 // ways intersect 291 return null; 292 } 293 } 294 } 295 296 return new Pair<>(outerGood, innerCandidates); 297 } 298 299 /** 300 * Collects outer way and corresponding inner ways from all boundaries. 301 * @param boundaryWays boundary ways 302 * @return the outermostWay, or {@code null} if intersection found. 303 */ 304 private static List<PolygonLevel> findOuterWaysMultiThread(List<JoinedPolygon> boundaryWays) { 305 final List<PolygonLevel> result = new ArrayList<>(); 306 final List<Worker> tasks = new ArrayList<>(); 307 final int bucketsize = Math.max(32, boundaryWays.size()/THREAD_POOL.a/3); 308 final int noBuckets = (boundaryWays.size() + bucketsize - 1) / bucketsize; 309 final boolean singleThread = THREAD_POOL.a == 1 || noBuckets == 1; 310 for (int i = 0; i < noBuckets; i++) { 311 int from = i*bucketsize; 312 int to = Math.min((i+1)*bucketsize, boundaryWays.size()); 313 List<PolygonLevel> target = singleThread ? result : new ArrayList<PolygonLevel>(to - from); 314 tasks.add(new Worker(boundaryWays, from, to, target)); 315 } 316 if (singleThread) { 317 try { 318 for (Worker task : tasks) { 319 if (task.call() == null) { 320 return null; 321 } 322 } 323 } catch (Exception ex) { 324 throw new RuntimeException(ex); 325 } 326 } else if (!tasks.isEmpty()) { 327 try { 328 for (Future<List<PolygonLevel>> future : THREAD_POOL.b.invokeAll(tasks)) { 329 List<PolygonLevel> res = future.get(); 330 if (res == null) { 331 return null; 332 } 333 result.addAll(res); 334 } 335 } catch (InterruptedException | ExecutionException ex) { 336 throw new RuntimeException(ex); 337 } 338 } 339 return result; 340 } 341 342 private static class Worker implements Callable<List<PolygonLevel>> { 343 344 private final List<JoinedPolygon> input; 345 private final int from; 346 private final int to; 347 private final List<PolygonLevel> output; 348 349 Worker(List<JoinedPolygon> input, int from, int to, List<PolygonLevel> output) { 350 this.input = input; 351 this.from = from; 352 this.to = to; 353 this.output = output; 354 } 355 356 /** 357 * Collects outer way and corresponding inner ways from all boundaries. 358 * @param level nesting level 359 * @param boundaryWays boundary ways 360 * @return the outermostWay, or {@code null} if intersection found. 361 */ 362 private static List<PolygonLevel> findOuterWaysRecursive(int level, List<JoinedPolygon> boundaryWays) { 363 364 final List<PolygonLevel> result = new ArrayList<>(); 365 366 for (JoinedPolygon outerWay : boundaryWays) { 367 if (processOuterWay(level, boundaryWays, result, outerWay) == null) { 368 return null; 369 } 370 } 371 372 return result; 373 } 374 375 private static List<PolygonLevel> processOuterWay(int level, List<JoinedPolygon> boundaryWays, 376 final List<PolygonLevel> result, JoinedPolygon outerWay) { 377 Pair<Boolean, List<JoinedPolygon>> p = findInnerWaysCandidates(outerWay, boundaryWays); 378 if (p == null) { 379 // ways intersect 380 return null; 381 } 382 383 if (p.a) { 384 //add new outer polygon 385 PolygonLevel pol = new PolygonLevel(outerWay, level); 386 387 //process inner ways 388 if (!p.b.isEmpty()) { 389 List<PolygonLevel> innerList = findOuterWaysRecursive(level + 1, p.b); 390 if (innerList == null) { 391 return null; //intersection found 392 } 393 394 result.addAll(innerList); 395 396 for (PolygonLevel pl : innerList) { 397 if (pl.level == level + 1) { 398 pol.innerWays.add(pl.outerWay); 399 } 400 } 401 } 402 403 result.add(pol); 404 } 405 return result; 406 } 407 408 @Override 409 public List<PolygonLevel> call() throws Exception { 410 for (int i = from; i < to; i++) { 411 if (processOuterWay(0, input, output, input.get(i)) == null) { 412 return null; 413 } 414 } 415 return output; 416 } 417 } 418}