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

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

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