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

Last change on this file since 30145 was 29535, checked in by donvip, 12 years ago

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