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