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

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

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