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

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

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