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