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.Main; 014import org.openstreetmap.josm.actions.CombineWayAction; 015import org.openstreetmap.josm.command.AddCommand; 016import org.openstreetmap.josm.command.Command; 017import org.openstreetmap.josm.command.SequenceCommand; 018import org.openstreetmap.josm.data.coor.EastNorth; 019import org.openstreetmap.josm.data.osm.Node; 020import org.openstreetmap.josm.data.osm.Way; 021import org.openstreetmap.josm.tools.Geometry; 022 023/** 024 * Helper for ParallelWayAction 025 * 026 * @author Ole Jørgen Brønner (olejorgenb) 027 */ 028public class ParallelWays { 029 private final List<Way> ways; 030 private final List<Node> sortedNodes; 031 032 private final int nodeCount; 033 034 private final EastNorth[] pts; 035 private final EastNorth[] normals; 036 037 // Need a reference way to determine the direction of the offset when we manage multiple ways 038 public ParallelWays(Collection<Way> sourceWays, boolean copyTags, int refWayIndex) { 039 // Possible/sensible to use PrimetiveDeepCopy here? 040 041 // Make a deep copy of the ways, keeping the copied ways connected 042 // TODO: This assumes the first/last nodes of the ways are the only possible shared nodes. 043 Map<Node, Node> splitNodeMap = new HashMap<>(sourceWays.size()); 044 for (Way w : sourceWays) { 045 if (!splitNodeMap.containsKey(w.firstNode())) { 046 splitNodeMap.put(w.firstNode(), copyNode(w.firstNode(), copyTags)); 047 } 048 if (!splitNodeMap.containsKey(w.lastNode())) { 049 splitNodeMap.put(w.lastNode(), copyNode(w.lastNode(), copyTags)); 050 } 051 } 052 ways = new ArrayList<>(sourceWays.size()); 053 for (Way w : sourceWays) { 054 Way wCopy = new Way(); 055 wCopy.addNode(splitNodeMap.get(w.firstNode())); 056 for (int i = 1; i < w.getNodesCount() - 1; i++) { 057 wCopy.addNode(copyNode(w.getNode(i), copyTags)); 058 } 059 wCopy.addNode(splitNodeMap.get(w.lastNode())); 060 if (copyTags) { 061 wCopy.setKeys(w.getKeys()); 062 } 063 ways.add(wCopy); 064 } 065 sourceWays = null; // Ensure that we only use the copies from now 066 067 // Find a linear ordering of the nodes. Fail if there isn't one. 068 CombineWayAction.NodeGraph nodeGraph = CombineWayAction.NodeGraph.createUndirectedGraphFromNodeWays(ways); 069 List<Node> sortedNodesPath = nodeGraph.buildSpanningPath(); 070 if (sortedNodesPath == null) 071 throw new IllegalArgumentException("Ways must have spanning path"); // Create a dedicated exception? 072 073 // Fix #8631 - Remove duplicated nodes from graph to be robust with self-intersecting ways 074 Set<Node> removedNodes = new HashSet<>(); 075 sortedNodes = new ArrayList<>(); 076 for (int i = 0; i < sortedNodesPath.size(); i++) { 077 Node n = sortedNodesPath.get(i); 078 if (i < sortedNodesPath.size()-1) { 079 if (sortedNodesPath.get(i+1).getCoor().equals(n.getCoor())) { 080 removedNodes.add(n); 081 for (Way w : ways) { 082 w.removeNode(n); 083 } 084 continue; 085 } 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 public boolean isClosedPath() { 124 return sortedNodes.get(0) == sortedNodes.get(sortedNodes.size() - 1); 125 } 126 127 /** 128 * Offsets the way(s) d units. Positive d means to the left (relative to the reference way) 129 * @param d offset 130 */ 131 public void changeOffset(double d) { 132 // This is the core algorithm: 133 /* 1. Calculate a parallel line, offset by 'd', to each segment in the path 134 * 2. Find the intersection of lines belonging to neighboring segments. These become the new node positions 135 * 3. Do some special casing for closed paths 136 * 137 * Simple and probably not even close to optimal performance wise 138 */ 139 140 EastNorth[] ppts = new EastNorth[nodeCount]; 141 142 EastNorth prevA = pts[0].add(normals[0].scale(d)); 143 EastNorth prevB = pts[1].add(normals[0].scale(d)); 144 for (int i = 1; i < nodeCount - 1; i++) { 145 EastNorth A = pts[i].add(normals[i].scale(d)); 146 EastNorth B = pts[i + 1].add(normals[i].scale(d)); 147 if (Geometry.segmentsParallel(A, B, prevA, prevB)) { 148 ppts[i] = A; 149 } else { 150 ppts[i] = Geometry.getLineLineIntersection(A, B, prevA, prevB); 151 } 152 prevA = A; 153 prevB = B; 154 } 155 if (isClosedPath()) { 156 EastNorth A = pts[0].add(normals[0].scale(d)); 157 EastNorth B = pts[1].add(normals[0].scale(d)); 158 if (Geometry.segmentsParallel(A, B, prevA, prevB)) { 159 ppts[0] = A; 160 } else { 161 ppts[0] = Geometry.getLineLineIntersection(A, B, prevA, prevB); 162 } 163 ppts[nodeCount - 1] = ppts[0]; 164 } else { 165 ppts[0] = pts[0].add(normals[0].scale(d)); 166 ppts[nodeCount - 1] = pts[nodeCount - 1].add(normals[nodeCount - 2].scale(d)); 167 } 168 169 for (int i = 0; i < nodeCount; i++) { 170 sortedNodes.get(i).setEastNorth(ppts[i]); 171 } 172 } 173 174 public void commit() { 175 SequenceCommand undoCommand = new SequenceCommand("Make parallel way(s)", makeAddWayAndNodesCommandList()); 176 Main.main.undoRedo.add(undoCommand); 177 } 178 179 private List<Command> makeAddWayAndNodesCommandList() { 180 List<Command> commands = new ArrayList<>(sortedNodes.size() + ways.size()); 181 for (int i = 0; i < sortedNodes.size() - (isClosedPath() ? 1 : 0); i++) { 182 commands.add(new AddCommand(sortedNodes.get(i))); 183 } 184 for (Way w : ways) { 185 commands.add(new AddCommand(w)); 186 } 187 return commands; 188 } 189 190 private static Node copyNode(Node source, boolean copyTags) { 191 if (copyTags) 192 return new Node(source, true); 193 else { 194 Node n = new Node(); 195 n.setCoor(source.getCoor()); 196 return n; 197 } 198 } 199 200 public final List<Way> getWays() { 201 return ways; 202 } 203}