001// License: GPL. See LICENSE file for details. 002package org.openstreetmap.josm.actions.mapmode; 003 004import java.util.ArrayList; 005import java.util.Collection; 006import java.util.Collections; 007import java.util.HashMap; 008import java.util.HashSet; 009import java.util.List; 010import java.util.Set; 011 012import org.openstreetmap.josm.Main; 013import org.openstreetmap.josm.actions.CombineWayAction; 014import org.openstreetmap.josm.command.AddCommand; 015import org.openstreetmap.josm.command.Command; 016import org.openstreetmap.josm.command.SequenceCommand; 017import org.openstreetmap.josm.data.coor.EastNorth; 018import org.openstreetmap.josm.data.osm.Node; 019import org.openstreetmap.josm.data.osm.Way; 020import org.openstreetmap.josm.tools.Geometry; 021 022/** 023 * Helper for ParallelWayAction 024 * 025 * @author Ole Jørgen Brønner (olejorgenb) 026 */ 027public class ParallelWays { 028 final List<Way> ways; 029 private final List<Node> sortedNodes; 030 031 private final int nodeCount; 032 033 private final EastNorth[] pts; 034 private final EastNorth[] normals; 035 036 // Need a reference way to determine the direction of the offset when we manage multiple ways 037 public ParallelWays(Collection<Way> sourceWays, boolean copyTags, int refWayIndex) { 038 // Possible/sensible to use PrimetiveDeepCopy here? 039 040 // Make a deep copy of the ways, keeping the copied ways connected 041 // TODO: This assumes the first/last nodes of the ways are the only possible shared nodes. 042 HashMap<Node, Node> splitNodeMap = new HashMap<>(sourceWays.size()); 043 for (Way w : sourceWays) { 044 if (!splitNodeMap.containsKey(w.firstNode())) { 045 splitNodeMap.put(w.firstNode(), copyNode(w.firstNode(), copyTags)); 046 } 047 if (!splitNodeMap.containsKey(w.lastNode())) { 048 splitNodeMap.put(w.lastNode(), copyNode(w.lastNode(), copyTags)); 049 } 050 } 051 ways = new ArrayList<>(sourceWays.size()); 052 for (Way w : sourceWays) { 053 Way wCopy = new Way(); 054 wCopy.addNode(splitNodeMap.get(w.firstNode())); 055 for (int i = 1; i < w.getNodesCount() - 1; i++) { 056 wCopy.addNode(copyNode(w.getNode(i), copyTags)); 057 } 058 wCopy.addNode(splitNodeMap.get(w.lastNode())); 059 if (copyTags) { 060 wCopy.setKeys(w.getKeys()); 061 } 062 ways.add(wCopy); 063 } 064 sourceWays = null; // Ensure that we only use the copies from now 065 066 // Find a linear ordering of the nodes. Fail if there isn't one. 067 CombineWayAction.NodeGraph nodeGraph = CombineWayAction.NodeGraph.createUndirectedGraphFromNodeWays(ways); 068 List<Node> sortedNodesPath = nodeGraph.buildSpanningPath(); 069 if (sortedNodesPath == null) 070 throw new IllegalArgumentException("Ways must have spanning path"); // Create a dedicated exception? 071 072 // Fix #8631 - Remove duplicated nodes from graph to be robust with self-intersecting ways 073 Set<Node> removedNodes = new HashSet<>(); 074 sortedNodes = new ArrayList<>(); 075 for (int i = 0; i < sortedNodesPath.size(); i++) { 076 Node n = sortedNodesPath.get(i); 077 if (i < sortedNodesPath.size()-1) { 078 if (sortedNodesPath.get(i+1).getCoor().equals(n.getCoor())) { 079 removedNodes.add(n); 080 for (Way w : ways) 081 w.removeNode(n); 082 continue; 083 } 084 } 085 if (!removedNodes.contains(n)) { 086 sortedNodes.add(n); 087 } 088 } 089 090 // Ugly method of ensuring that the offset isn't inverted. I'm sure there is a better and more elegant way, but I'm starting to get sleepy, so I do this for now. 091 Way refWay = ways.get(refWayIndex); 092 boolean refWayReversed = true; 093 for (int i = 0; i < sortedNodes.size() - 1; i++) { 094 if (sortedNodes.get(i) == refWay.firstNode() && sortedNodes.get(i + 1) == refWay.getNode(1)) { 095 refWayReversed = false; 096 break; 097 } 098 } 099 if (refWayReversed) { 100 Collections.reverse(sortedNodes); // need to keep the orientation of the reference way. 101 } 102 103 // Initialize the required parameters. (segment normals, etc.) 104 nodeCount = sortedNodes.size(); 105 pts = new EastNorth[nodeCount]; 106 normals = new EastNorth[nodeCount - 1]; 107 int i = 0; 108 for (Node n : sortedNodes) { 109 EastNorth t = n.getEastNorth(); 110 pts[i] = t; 111 i++; 112 } 113 for (i = 0; i < nodeCount - 1; i++) { 114 double dx = pts[i + 1].getX() - pts[i].getX(); 115 double dy = pts[i + 1].getY() - pts[i].getY(); 116 double len = Math.sqrt(dx * dx + dy * dy); 117 normals[i] = new EastNorth(-dy / len, dx / len); 118 } 119 } 120 121 public boolean isClosedPath() { 122 return sortedNodes.get(0) == sortedNodes.get(sortedNodes.size() - 1); 123 } 124 125 /** 126 * Offsets the way(s) d units. Positive d means to the left (relative to the reference way) 127 * @param d 128 */ 129 public void changeOffset(double d) { 130 // This is the core algorithm: 131 /* 1. Calculate a parallel line, offset by 'd', to each segment in the path 132 * 2. Find the intersection of lines belonging to neighboring segments. These become the new node positions 133 * 3. Do some special casing for closed paths 134 * 135 * Simple and probably not even close to optimal performance wise 136 */ 137 138 EastNorth[] ppts = new EastNorth[nodeCount]; 139 140 EastNorth prevA = pts[0].add(normals[0].scale(d)); 141 EastNorth prevB = pts[1].add(normals[0].scale(d)); 142 for (int i = 1; i < nodeCount - 1; i++) { 143 EastNorth A = pts[i].add(normals[i].scale(d)); 144 EastNorth B = pts[i + 1].add(normals[i].scale(d)); 145 if (Geometry.segmentsParallel(A, B, prevA, prevB)) { 146 ppts[i] = A; 147 } else { 148 ppts[i] = Geometry.getLineLineIntersection(A, B, prevA, prevB); 149 } 150 prevA = A; 151 prevB = B; 152 } 153 if (isClosedPath()) { 154 EastNorth A = pts[0].add(normals[0].scale(d)); 155 EastNorth B = pts[1].add(normals[0].scale(d)); 156 if (Geometry.segmentsParallel(A, B, prevA, prevB)) { 157 ppts[0] = A; 158 } else { 159 ppts[0] = Geometry.getLineLineIntersection(A, B, prevA, prevB); 160 } 161 ppts[nodeCount - 1] = ppts[0]; 162 } else { 163 ppts[0] = pts[0].add(normals[0].scale(d)); 164 ppts[nodeCount - 1] = pts[nodeCount - 1].add(normals[nodeCount - 2].scale(d)); 165 } 166 167 for (int i = 0; i < nodeCount; i++) { 168 sortedNodes.get(i).setEastNorth(ppts[i]); 169 } 170 } 171 172 public void commit() { 173 SequenceCommand undoCommand = new SequenceCommand("Make parallel way(s)", makeAddWayAndNodesCommandList()); 174 Main.main.undoRedo.add(undoCommand); 175 } 176 177 private List<Command> makeAddWayAndNodesCommandList() { 178 List<Command> commands = new ArrayList<>(sortedNodes.size() + ways.size()); 179 for (int i = 0; i < sortedNodes.size() - (isClosedPath() ? 1 : 0); i++) { 180 commands.add(new AddCommand(sortedNodes.get(i))); 181 } 182 for (Way w : ways) { 183 commands.add(new AddCommand(w)); 184 } 185 return commands; 186 } 187 188 private static Node copyNode(Node source, boolean copyTags) { 189 if (copyTags) 190 return new Node(source, true); 191 else { 192 Node n = new Node(); 193 n.setCoor(source.getCoor()); 194 return n; 195 } 196 } 197}