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

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

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