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