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

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

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