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

Last change on this file since 32395 was 32395, checked in by donvip, 8 years ago

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