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

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

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