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

Last change on this file since 36134 was 36134, checked in by taylor.smock, 2 years ago

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