source: osm/applications/editors/josm/plugins/reltoolbox/src/relcontext/actions/TheRing.java@ 26888

Last change on this file since 26888 was 26888, checked in by zverik, 14 years ago

It's alive! ALIVE!
File size: 19.1 KB
Line 
1package relcontext.actions;
2
3import java.util.*;
4import javax.swing.JOptionPane;
5import org.openstreetmap.josm.Main;
6import org.openstreetmap.josm.command.*;
7import org.openstreetmap.josm.data.coor.EastNorth;
8import org.openstreetmap.josm.data.osm.*;
9import org.openstreetmap.josm.tools.Geometry;
10import org.openstreetmap.josm.tools.Geometry.PolygonIntersection;
11
12/**
13 * One ring that contains segments forming an outer way of multipolygon.
14 * This class is used in {@link CreateMultipolygonAction#makeManySimpleMultipolygons(java.util.Collection)}.
15 *
16 * @author Zverik
17 */
18public class TheRing {
19 private static final String PREF_MULTIPOLY = "reltoolbox.multipolygon.";
20
21 private Way source;
22 private List<RingSegment> segments;
23 private Relation relation = null;
24
25 public TheRing( Way source ) {
26 this.source = source;
27 segments = new ArrayList<RingSegment>(1);
28 segments.add(new RingSegment(source));
29 }
30
31 public static boolean areAllOfThoseRings( Collection<Way> ways ) {
32 List<Way> rings = new ArrayList<Way>();
33 for( Way way : ways ) {
34 if( way.isClosed() )
35 rings.add(way);
36 else
37 return false;
38 }
39 if( rings.isEmpty() || ways.size() == 1 )
40 return false;
41
42 // check for non-containment of rings
43 for( int i = 0; i < rings.size() - 1; i++ ) {
44 for( int j = i + 1; j < rings.size(); j++ ) {
45 PolygonIntersection intersection = Geometry.polygonIntersection(rings.get(i).getNodes(), rings.get(j).getNodes());
46 if( intersection == PolygonIntersection.FIRST_INSIDE_SECOND || intersection == PolygonIntersection.SECOND_INSIDE_FIRST )
47 return false;
48 }
49 }
50
51 return true;
52 }
53
54 /**
55 * Creates ALOT of Multipolygons and pets him gently.
56 * @return list of new relations.
57 */
58 public static List<Relation> makeManySimpleMultipolygons( Collection<Way> selection, List<Command> commands ) {
59 System.out.println("---------------------------------------");
60 List<TheRing> rings = new ArrayList<TheRing>(selection.size());
61 for( Way w : selection )
62 rings.add(new TheRing(w));
63 for( int i = 0; i < rings.size() - 1; i++ )
64 for( int j = i + 1; j < rings.size(); j++ )
65 rings.get(i).collide(rings.get(j));
66 redistributeSegments(rings);
67 List<Relation> relations = new ArrayList<Relation>();
68 Map<Relation, Relation> relationCache = new HashMap<Relation, Relation>();
69 for( TheRing r : rings ) {
70 commands.addAll(r.getCommands(relationCache));
71 relations.add(r.getRelation());
72 }
73 updateCommandsWithRelations(commands, relationCache);
74 return relations;
75 }
76
77 public void collide( TheRing other ) {
78 boolean collideNoted = false;
79 for( int i = 0; i < segments.size(); i++ ) {
80 RingSegment segment1 = segments.get(i);
81 if( !segment1.isReference() ) {
82 for( int j = 0; j < other.segments.size(); j++ ) {
83 RingSegment segment2 = other.segments.get(j);
84 if( !segment2.isReference() ) {
85 System.out.println("Comparing " + segment1 + " and " + segment2);
86 Node[] split = getSplitNodes(segment1.getNodes(), segment2.getNodes(), segment1.isRing(), segment2.isRing());
87 if( split != null ) {
88 if( !collideNoted ) {
89 System.out.println("Rings for ways " + source.getUniqueId() + " and " + other.source.getUniqueId() + " collide.");
90 collideNoted = true;
91 }
92 RingSegment segment = splitRingAt(i, split[0], split[1]);
93 RingSegment otherSegment = other.splitRingAt(j, split[2], split[3]);
94 if( !areSegmentsEqual(segment, otherSegment) )
95 throw new IllegalArgumentException("Error: algorithm gave incorrect segments: " + segment + " and " + otherSegment);
96 segment.makeReference(otherSegment);
97 }
98 }
99 if( segment1.isReference() )
100 break;
101 }
102 }
103 }
104 }
105
106 /**
107 * Returns array of {start1, last1, start2, last2} or null if there is no common nodes.
108 */
109 public static Node[] getSplitNodes( List<Node> nodes1, List<Node> nodes2, boolean isRing1, boolean isRing2 ) {
110 int pos = 0;
111 while( pos < nodes1.size() && !nodes2.contains(nodes1.get(pos)) )
112 pos++;
113 boolean collideFound = pos == nodes1.size();
114 if( pos == 0 && isRing1 ) {
115 // rewind a bit
116 pos = nodes1.size() - 1;
117 while( pos > 0 && nodes2.contains(nodes1.get(pos)) )
118 pos--;
119 if( pos == 0 ) {
120 JOptionPane.showMessageDialog(Main.parent, "Two rings are equal, and this must not be.", "Multipolygon from rings", JOptionPane.ERROR_MESSAGE);
121 return null;
122 }
123 pos = pos == nodes1.size() - 1 ? 0 : pos + 1;
124 }
125 int firstPos = isRing1 ? pos : nodes1.size();
126 while( !collideFound ) {
127 System.out.println("pos=" + pos);
128 int start1 = pos;
129 int start2 = nodes2.indexOf(nodes1.get(start1));
130 int last1 = incrementBy(start1, 1, nodes1.size(), isRing1);
131 int last2 = start2;
132 int increment2 = 0;
133 if( last1 >= 0 ) {
134 last2 = incrementBy(start2, -1, nodes2.size(), isRing2);
135 if( last2 >= 0 && nodes1.get(last1).equals(nodes2.get(last2)) )
136 increment2 = -1;
137 else {
138 last2 = incrementBy(start2, 1, nodes2.size(), isRing2);
139 if( last2 >= 0 && nodes1.get(last1).equals(nodes2.get(last2)) )
140 increment2 = 1;
141 }
142 }
143 System.out.println("last1=" + last1 + " last2=" + last2 + " increment2=" + increment2);
144 if( increment2 != 0 ) {
145 // find the first nodes
146 boolean reachedEnd = false;
147 while( !reachedEnd ) {
148 int newLast1 = incrementBy(last1, 1, nodes1.size(), isRing1);
149 int newLast2 = incrementBy(last2, increment2, nodes2.size(), isRing2);
150 if( newLast1 < 0 || newLast2 < 0 || !nodes1.get(newLast1).equals(nodes2.get(newLast2)) )
151 reachedEnd = true;
152 else {
153 last1 = newLast1;
154 last2 = newLast2;
155 }
156 }
157 System.out.println("last1=" + last1 + " last2=" + last2);
158 if( increment2 < 0 ) {
159 int tmp = start2;
160 start2 = last2;
161 last2 = tmp;
162 }
163 return new Node[] {nodes1.get(start1), nodes1.get(last1), nodes2.get(start2), nodes2.get(last2)};
164 } else {
165 pos = last1;
166 while( pos != firstPos && pos >= 0 && !nodes2.contains(nodes1.get(pos)) )
167 pos = incrementBy(pos, 1, nodes1.size(), isRing1);
168 if( pos < 0 || pos == firstPos || !nodes2.contains(nodes1.get(pos)) )
169 collideFound = true;
170 }
171 }
172 return null;
173 }
174
175 private static int incrementBy( int value, int increment, int limit1, boolean isRing ) {
176 int result = value + increment;
177 if( result < 0 )
178 return isRing ? result + limit1 : -1;
179 else if( result >= limit1 )
180 return isRing ? result - limit1 : -1;
181 else
182 return result;
183 }
184
185 private boolean areSegmentsEqual( RingSegment seg1, RingSegment seg2 ) {
186 List<Node> nodes1 = seg1.getNodes();
187 List<Node> nodes2 = seg2.getNodes();
188 int size = nodes1.size();
189 if( size != nodes2.size() )
190 return false;
191 boolean reverse = size > 1 && !nodes1.get(0).equals(nodes2.get(0));
192 for( int i = 0; i < size; i++ )
193 if( !nodes1.get(i).equals(nodes2.get(reverse ? size-1-i : i)) )
194 return false;
195 return true;
196 }
197
198 /**
199 * Split the segment in this ring at those nodes.
200 * @return The segment between nodes.
201 */
202 private RingSegment splitRingAt( int segmentIndex, Node n1, Node n2 ) {
203 if( n1.equals(n2) )
204 throw new IllegalArgumentException("Both nodes are equal, id=" + n1.getUniqueId());
205 RingSegment segment = segments.get(segmentIndex);
206 boolean isRing = segment.isRing();
207 System.out.println("Split segment " + segment + " at nodes " + n1.getUniqueId() + " and " + n2.getUniqueId());
208 boolean reversed = segment.getNodes().indexOf(n2) < segment.getNodes().indexOf(n1);
209 if( reversed && !isRing ) {
210 // order nodes
211 Node tmp = n1;
212 n1 = n2;
213 n2 = tmp;
214 }
215 RingSegment secondPart = isRing ? segment.split(n1, n2) : segment.split(n1);
216 // if secondPart == null, then n1 == firstNode
217 RingSegment thirdPart = isRing ? null : secondPart == null ? segment.split(n2) : secondPart.split(n2);
218 // if secondPart == null, then thirdPart is between n1 and n2
219 // otherwise, thirdPart is between n2 and lastNode
220 // if thirdPart == null, then n2 == lastNode
221 int pos = segmentIndex + 1;
222 if( secondPart != null )
223 segments.add(pos++, secondPart);
224 if( thirdPart != null )
225 segments.add(pos++, thirdPart);
226 return isRing || secondPart == null ? segment : secondPart;
227 }
228
229 /**
230 * Tries to arrange segments in order for each ring to have at least one.
231 * Also, sets source way for all rings.
232 *
233 * If this method is not called, do not forget to call {@link #putSourceWayFirst()} for all rings.
234 */
235 public static void redistributeSegments( List<TheRing> rings ) {
236 // build segments map
237 Map<RingSegment, TheRing> segmentMap = new HashMap<RingSegment, TheRing>();
238 for( TheRing ring : rings )
239 for( RingSegment seg : ring.segments )
240 if( !seg.isReference() )
241 segmentMap.put(seg, ring);
242
243 // rearrange references
244 for( int i = 0; i < rings.size(); i++ ) {
245 TheRing ring = rings.get(i);
246 if( ring.countNonReferenceSegments() == 0 ) {
247 // need to find one non-reference segment
248 for( RingSegment seg : ring.segments ) {
249 TheRing otherRing = segmentMap.get(seg.references);
250 if( otherRing.countNonReferenceSegments() > 1 ) {
251 // we could check for >0, but it is prone to deadlocking
252 seg.swapReference();
253 }
254 }
255 }
256 }
257
258 // initializing source way for each ring
259 for( TheRing ring : rings )
260 ring.putSourceWayFirst();
261 }
262
263 private int countNonReferenceSegments() {
264 int count = 0;
265 for( RingSegment seg : segments )
266 if( !seg.isReference() )
267 count++;
268 return count;
269 }
270
271 public void putSourceWayFirst() {
272 for( RingSegment seg : segments ) {
273 if( !seg.isReference() ) {
274 seg.overrideWay(source);
275 return;
276 }
277 }
278 }
279
280 public List<Command> getCommands() {
281 return getCommands(true, null);
282 }
283
284 public List<Command> getCommands( Map<Relation, Relation> relationChangeMap ) {
285 return getCommands(true, relationChangeMap);
286 }
287
288 /**
289 * Returns a list of commands to make a new relation and all newly created ways.
290 * The first way is copied from the source one, ChangeCommand is issued in this case.
291 */
292 public List<Command> getCommands( boolean createMultipolygon, Map<Relation, Relation> relationChangeMap ) {
293 Way sourceCopy = new Way(source);
294 if( createMultipolygon ) {
295 Collection<String> linearTags = Main.pref.getCollection(PREF_MULTIPOLY + "lineartags", CreateMultipolygonAction.DEFAULT_LINEAR_TAGS);
296 relation = new Relation();
297 relation.put("type", "multipolygon");
298 for( String key : sourceCopy.keySet() ) {
299 if( !linearTags.contains(key) ) {
300 relation.put(key, sourceCopy.get(key));
301 sourceCopy.remove(key);
302 }
303 }
304 }
305
306 // build a map of referencing relations
307 Map<Relation, Integer> referencingRelations = new HashMap<Relation, Integer>();
308 List<Command> relationCommands = new ArrayList<Command>();
309 for( OsmPrimitive p : source.getReferrers() ) {
310 if( p instanceof Relation ) {
311 Relation rel = null;
312 if( relationChangeMap != null ) {
313 if( relationChangeMap.containsKey((Relation)p) )
314 rel = relationChangeMap.get((Relation)p);
315 else {
316 rel = new Relation((Relation)p);
317 relationChangeMap.put((Relation)p, rel);
318 }
319 } else {
320 rel = new Relation((Relation)p);
321 relationCommands.add(new ChangeCommand((Relation)p, rel));
322 }
323 for( int i = 0; i < rel.getMembersCount(); i++ )
324 if( rel.getMember(i).getMember().equals(source) )
325 referencingRelations.put(rel, Integer.valueOf(i));
326 }
327 }
328 // todo: когда два кольца меняют одно и то же отношение, в список команд добавляется
329 // изменение базового отношения на новое, а не предыдущего
330 // поэтому сохраняется только первое изменение
331
332 List<Command> commands = new ArrayList<Command>();
333 boolean foundOwnWay = false;
334 for( RingSegment seg : segments ) {
335 boolean needAdding = !seg.isWayConstructed();
336 Way w = seg.constructWay(seg.isReference() ? null : sourceCopy);
337 if( needAdding )
338 commands.add(new AddCommand(w));
339 if( w.equals(source) ) {
340 if( createMultipolygon || !seg.getWayNodes().equals(source.getNodes()) ) {
341 sourceCopy.setNodes(seg.getWayNodes());
342 commands.add(new ChangeCommand(source, sourceCopy));
343 }
344 foundOwnWay = true;
345 } else {
346 for( Relation rel : referencingRelations.keySet() ) {
347 int relIndex = referencingRelations.get(rel);
348 rel.addMember(new RelationMember(rel.getMember(relIndex).getRole(), w));
349 }
350 }
351 if( createMultipolygon )
352 relation.addMember(new RelationMember("outer", w));
353 }
354 if( !foundOwnWay )
355 commands.add(new DeleteCommand(source));
356 commands.addAll(relationCommands);
357 if( createMultipolygon )
358 commands.add(new AddCommand(relation));
359 return commands;
360 }
361
362 public static void updateCommandsWithRelations( List<Command> commands, Map<Relation, Relation> relationCache ) {
363 for( Relation src : relationCache.keySet() )
364 commands.add(new ChangeCommand(src, relationCache.get(src)));
365 }
366
367 /**
368 * Returns the relation created in {@link #getCommands()}.
369 */
370 public Relation getRelation() {
371 return relation;
372 }
373
374 @Override
375 public String toString() {
376 StringBuilder sb = new StringBuilder("TheRing@");
377 sb.append(this.hashCode()).append('[').append("wayId: ").append(source == null ? "null" : source.getUniqueId()).append("; segments: ");
378 if( segments.isEmpty() )
379 sb.append("empty");
380 else {
381 sb.append(segments.get(0));
382 for( int i = 1; i < segments.size(); i++ )
383 sb.append(", ").append(segments.get(i));
384 }
385 return sb.append(']').toString();
386 }
387
388 /**
389 * Appends "append" to "base" so the closed polygon forms.
390 */
391 private static void closePolygon( List<Node> base, List<Node> append ) {
392 if( append.get(0).equals(base.get(0)) && append.get(append.size() - 1).equals(base.get(base.size() - 1)) ) {
393 List<Node> ap2 = new ArrayList<Node>(append);
394 Collections.reverse(ap2);
395 append = ap2;
396 }
397 base.remove(base.size() - 1);
398 base.addAll(append);
399 }
400
401 /**
402 * Checks if a middle point between two nodes is inside a polygon. Useful to check if the way is inside.
403 */
404 private static boolean segmentInsidePolygon( Node n1, Node n2, List<Node> polygon ) {
405 EastNorth en1 = n1.getEastNorth();
406 EastNorth en2 = n2.getEastNorth();
407 Node testNode = new Node(new EastNorth((en1.east() + en2.east()) / 2.0, (en1.north() + en2.north()) / 2.0));
408 return Geometry.nodeInsidePolygon(testNode, polygon);
409 }
410
411 private static class RingSegment {
412 private List<Node> nodes;
413 private RingSegment references;
414 private Way resultingWay = null;
415 private boolean wasTemplateApplied = false;
416 private boolean isRing;
417
418 private RingSegment() {
419 }
420
421 public RingSegment( Way w ) {
422 this(w.getNodes());
423 }
424
425 public RingSegment( List<Node> nodes ) {
426 this.nodes = nodes;
427 isRing = nodes.size() > 1 && nodes.get(0).equals(nodes.get(nodes.size() - 1));
428 if( isRing )
429 nodes.remove(nodes.size() - 1);
430 references = null;
431 }
432
433 public RingSegment( RingSegment ref ) {
434 this.nodes = null;
435 this.references = ref;
436 }
437
438 /**
439 * Splits this segment at node n. Retains nodes 0..n and moves
440 * nodes n..N to a separate segment that is returned.
441 * @param n node at which to split.
442 * @return new segment, {@code null} if splitting is unnecessary.
443 */
444 public RingSegment split( Node n ) {
445 if( nodes == null )
446 throw new IllegalArgumentException("Cannot split segment: it is a reference");
447 int pos = nodes.indexOf(n);
448 if( pos <= 0 || pos >= nodes.size() - 1 )
449 return null;
450 List<Node> newNodes = new ArrayList<Node>(nodes.subList(pos, nodes.size()));
451 nodes.subList(pos + 1, nodes.size()).clear();
452 return new RingSegment(newNodes);
453 }
454
455 /**
456 * Split this segment as a way at two nodes. If one of them is null or at the end,
457 * split as an arc. Note: order of nodes is important.
458 * @return A new segment from n2 to n1.
459 */
460 public RingSegment split( Node n1, Node n2 ) {
461 if( nodes == null )
462 throw new IllegalArgumentException("Cannot split segment: it is a reference");
463 if( !isRing ) {
464 if( n1 == null || nodes.get(0).equals(n1) || nodes.get(nodes.size() - 1).equals(n1) )
465 return split(n2);
466 if( n2 == null || nodes.get(0).equals(n2) || nodes.get(nodes.size() - 1).equals(n2) )
467 return split(n1);
468 throw new IllegalArgumentException("Split for two nodes is called for not-ring: " + this);
469 }
470 int pos1 = nodes.indexOf(n1);
471 int pos2 = nodes.indexOf(n2);
472 if( pos1 == pos2 )
473 return null;
474
475 List<Node> newNodes = new ArrayList<Node>();
476 if( pos2 > pos1 ) {
477 newNodes.addAll(nodes.subList(pos2, nodes.size()));
478 newNodes.addAll(nodes.subList(0, pos1 + 1));
479 if( pos2 + 1 < nodes.size() )
480 nodes.subList(pos2 + 1, nodes.size()).clear();
481 if( pos1 > 0 )
482 nodes.subList(0, pos1).clear();
483 } else {
484 newNodes.addAll(nodes.subList(pos2, pos1 + 1));
485 nodes.addAll(new ArrayList<Node>(nodes.subList(0, pos2 + 1)));
486 nodes.subList(0, pos1).clear();
487 }
488 isRing = false;
489 return new RingSegment(newNodes);
490 }
491
492 public List<Node> getNodes() {
493 return nodes == null ? references.nodes : nodes;
494 }
495
496 public List<Node> getWayNodes() {
497 if( nodes == null )
498 throw new IllegalArgumentException("Won't give you wayNodes: it is a reference");
499 List<Node> wayNodes = new ArrayList<Node>(nodes);
500 if( isRing )
501 wayNodes.add(wayNodes.get(0));
502 return wayNodes;
503 }
504
505 public boolean isReference() {
506 return nodes == null;
507 }
508
509 public boolean isRing() {
510 return isRing;
511 }
512
513 public void makeReference( RingSegment segment ) {
514 System.out.println(this + " was made a reference to " + segment);
515 this.nodes = null;
516 this.references = segment;
517 }
518
519 public void swapReference() {
520 this.nodes = references.nodes;
521 references.nodes = null;
522 references.references = this;
523 this.references = null;
524 }
525
526 public boolean isWayConstructed() {
527 return isReference() ? references.isWayConstructed() : resultingWay != null;
528 }
529
530 public Way constructWay( Way template ) {
531 if( isReference() )
532 return references.constructWay(template);
533 if( resultingWay == null ) {
534 resultingWay = new Way();
535 resultingWay.setNodes(getWayNodes());
536 }
537 if( template != null && !wasTemplateApplied ) {
538 resultingWay.setKeys(template.getKeys());
539 wasTemplateApplied = true;
540 }
541 return resultingWay;
542 }
543
544 public void overrideWay( Way source ) {
545 if( isReference() )
546 references.overrideWay(source);
547 else {
548 resultingWay = source;
549 wasTemplateApplied = true;
550 }
551 }
552
553 /**
554 * Compares two segments with respect to referencing.
555 * @return true if ways are equals, or one references another.
556 */
557 public boolean isReferencingEqual( RingSegment other ) {
558 return this.equals(other) || (other.isReference() && other.references == this) || (isReference() && references == other);
559 }
560
561 @Override
562 public String toString() {
563 StringBuilder sb = new StringBuilder("RingSegment@");
564 sb.append(this.hashCode()).append('[');
565 if( isReference() )
566 sb.append("references ").append(references.hashCode());
567 else if( nodes.isEmpty() )
568 sb.append("empty");
569 else {
570 if( isRing )
571 sb.append("ring:");
572 sb.append(nodes.get(0).getUniqueId());
573 for( int i = 1; i < nodes.size(); i++ )
574 sb.append(',').append(nodes.get(i).getUniqueId());
575 }
576 return sb.append(']').toString();
577 }
578 }
579}
Note: See TracBrowser for help on using the repository browser.