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

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

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