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

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

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