001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.actions; 003 004import static org.openstreetmap.josm.gui.help.HelpUtil.ht; 005import static org.openstreetmap.josm.tools.I18n.tr; 006 007import java.awt.event.ActionEvent; 008import java.awt.event.KeyEvent; 009import java.util.ArrayList; 010import java.util.Collection; 011import java.util.HashMap; 012import java.util.HashSet; 013import java.util.List; 014import java.util.Map; 015import java.util.Set; 016 017import javax.swing.JOptionPane; 018 019import org.openstreetmap.josm.Main; 020import org.openstreetmap.josm.command.Command; 021import org.openstreetmap.josm.command.MoveCommand; 022import org.openstreetmap.josm.command.SequenceCommand; 023import org.openstreetmap.josm.data.coor.EastNorth; 024import org.openstreetmap.josm.data.osm.Node; 025import org.openstreetmap.josm.data.osm.OsmPrimitive; 026import org.openstreetmap.josm.data.osm.Way; 027import org.openstreetmap.josm.gui.Notification; 028import org.openstreetmap.josm.tools.Shortcut; 029 030/** 031 * Aligns all selected nodes into a straight line (useful for roads that should be straight, but have side roads and 032 * therefore need multiple nodes) 033 * 034 * <pre> 035 * Case 1: 1 or 2 ways selected and no nodes selected: align nodes of ways taking care of intersection. 036 * Case 2: Single node selected and no ways selected: align this node relative to all referrer ways (2 at most). 037 * Case 3: Single node and ways selected: align this node relative to selected ways. 038 * Case 4.1: Only nodes selected, part of a non-closed way: align these nodes on the line passing through the 039 * extremity nodes (most distant in the way sequence). See https://josm.openstreetmap.de/ticket/9605#comment:3 040 * Case 4.2: Only nodes selected, part of a closed way: align these nodes on the line passing through the most distant nodes. 041 * Case 4.3: Only nodes selected, part of multiple ways: align these nodes on the line passing through the most distant nodes. 042 * </pre> 043 * 044 * @author Matthew Newton 045 */ 046public final class AlignInLineAction extends JosmAction { 047 048 /** 049 * Constructs a new {@code AlignInLineAction}. 050 */ 051 public AlignInLineAction() { 052 super(tr("Align Nodes in Line"), "alignline", tr("Move the selected nodes in to a line."), 053 Shortcut.registerShortcut("tools:alignline", tr("Tool: {0}", tr("Align Nodes in Line")), KeyEvent.VK_L, Shortcut.DIRECT), true); 054 putValue("help", ht("/Action/AlignInLine")); 055 } 056 057 /** 058 * InvalidSelection exception has to be raised when action can't be perform 059 */ 060 private static class InvalidSelection extends Exception { 061 062 /** 063 * Create an InvalidSelection exception with default message 064 */ 065 InvalidSelection() { 066 super(tr("Please select at least three nodes.")); 067 } 068 069 /** 070 * Create an InvalidSelection exception with specific message 071 * @param msg Message that will be display to the user 072 */ 073 InvalidSelection(String msg) { 074 super(msg); 075 } 076 } 077 078 /** 079 * Return 2 nodes making up the line along which provided nodes must be aligned. 080 * 081 * @param nodes Nodes to be aligned. 082 * @return A array of two nodes. 083 */ 084 private static Node[] nodePairFurthestApart(List<Node> nodes) { 085 // Detect if selected nodes are on the same way. 086 087 // Get ways passing though all selected nodes. 088 Set<Way> waysRef = null; 089 for (Node n: nodes) { 090 Collection<Way> ref = OsmPrimitive.getFilteredList(n.getReferrers(), Way.class); 091 if (waysRef == null) 092 waysRef = new HashSet<>(ref); 093 else 094 waysRef.retainAll(ref); 095 } 096 097 // Nodes belongs to multiple ways, return most distant nodes. 098 if (waysRef.size() != 1) 099 return nodeFurthestAppart(nodes); 100 101 // All nodes are part of the same way. See #9605. 102 Way way = waysRef.iterator().next(); 103 104 if (way.isClosed()) { 105 // Align these nodes on the line passing through the most distant nodes. 106 return nodeFurthestAppart(nodes); 107 } 108 109 Node nodea = null; 110 Node nodeb = null; 111 112 // The way is open, align nodes on the line passing through the extremity nodes (most distant in the way 113 // sequence). See #9605#comment:3. 114 Set<Node> remainNodes = new HashSet<>(nodes); 115 for (Node n : way.getNodes()) { 116 if (!remainNodes.contains(n)) 117 continue; 118 if (nodea == null) 119 nodea = n; 120 if (remainNodes.size() == 1) { 121 nodeb = remainNodes.iterator().next(); 122 break; 123 } 124 remainNodes.remove(n); 125 } 126 127 return new Node[] {nodea, nodeb}; 128 } 129 130 /** 131 * Return the two nodes the most distant from the provided list. 132 * 133 * @param nodes List of nodes to analyze. 134 * @return An array containing the two most distant nodes. 135 */ 136 private static Node[] nodeFurthestAppart(List<Node> nodes) { 137 Node node1 = null, node2 = null; 138 double minSqDistance = 0; 139 int nb; 140 141 nb = nodes.size(); 142 for (int i = 0; i < nb - 1; i++) { 143 Node n = nodes.get(i); 144 for (int j = i + 1; j < nb; j++) { 145 Node m = nodes.get(j); 146 double sqDist = n.getEastNorth().distanceSq(m.getEastNorth()); 147 if (sqDist > minSqDistance) { 148 node1 = n; 149 node2 = m; 150 minSqDistance = sqDist; 151 } 152 } 153 } 154 155 return new Node[] {node1, node2}; 156 } 157 158 /** 159 * Operation depends on the selected objects: 160 */ 161 @Override 162 public void actionPerformed(ActionEvent e) { 163 if (!isEnabled()) 164 return; 165 166 List<Node> selectedNodes = new ArrayList<>(getCurrentDataSet().getSelectedNodes()); 167 List<Way> selectedWays = new ArrayList<>(getCurrentDataSet().getSelectedWays()); 168 169 try { 170 Command cmd = null; 171 // Decide what to align based on selection: 172 173 if (selectedNodes.isEmpty() && !selectedWays.isEmpty()) { 174 // Only ways selected -> For each way align their nodes taking care of intersection 175 cmd = alignMultiWay(selectedWays); 176 } else if (selectedNodes.size() == 1) { 177 // Only 1 node selected -> align this node relative to referers way 178 Node selectedNode = selectedNodes.get(0); 179 List<Way> involvedWays = null; 180 if (selectedWays.isEmpty()) 181 // No selected way, all way containing this node are used 182 involvedWays = OsmPrimitive.getFilteredList(selectedNode.getReferrers(), Way.class); 183 else 184 // Selected way, use only these ways 185 involvedWays = selectedWays; 186 List<Line> lines = getInvolvedLines(selectedNode, involvedWays); 187 if (lines.size() > 2 || lines.isEmpty()) 188 throw new InvalidSelection(); 189 cmd = alignSingleNode(selectedNodes.get(0), lines); 190 } else if (selectedNodes.size() >= 3) { 191 // More than 3 nodes and way(s) selected -> align selected nodes. Don't care of way(s). 192 cmd = alignOnlyNodes(selectedNodes); 193 } else { 194 // All others cases are invalid 195 throw new InvalidSelection(); 196 } 197 198 // Do it! 199 Main.main.undoRedo.add(cmd); 200 Main.map.repaint(); 201 202 } catch (InvalidSelection except) { 203 new Notification(except.getMessage()) 204 .setIcon(JOptionPane.INFORMATION_MESSAGE) 205 .show(); 206 } 207 } 208 209 /** 210 * Align nodes in case 3 or more nodes are selected. 211 * 212 * @param nodes Nodes to be aligned. 213 * @return Command that perform action. 214 * @throws InvalidSelection If the nodes have same coordinates. 215 */ 216 private static Command alignOnlyNodes(List<Node> nodes) throws InvalidSelection { 217 // Choose nodes used as anchor points for projection. 218 Node[] anchors = nodePairFurthestApart(nodes); 219 Collection<Command> cmds = new ArrayList<>(nodes.size()); 220 Line line = new Line(anchors[0], anchors[1]); 221 for (Node node: nodes) { 222 if (node != anchors[0] && node != anchors[1]) 223 cmds.add(line.projectionCommand(node)); 224 } 225 return new SequenceCommand(tr("Align Nodes in Line"), cmds); 226 } 227 228 /** 229 * Align way in case of multiple way #6819 230 * @param ways Collection of way to align 231 * @return Command that perform action 232 * @throws InvalidSelection if a polygon is selected, or if a node is used by 3 or more ways 233 */ 234 private static Command alignMultiWay(Collection<Way> ways) throws InvalidSelection { 235 // Collect all nodes and compute line equation 236 Set<Node> nodes = new HashSet<>(); 237 Map<Way, Line> lines = new HashMap<>(); 238 for (Way w: ways) { 239 if (w.isClosed()) 240 throw new InvalidSelection(tr("Can not align a polygon. Abort.")); 241 nodes.addAll(w.getNodes()); 242 lines.put(w, new Line(w)); 243 } 244 Collection<Command> cmds = new ArrayList<>(nodes.size()); 245 List<Way> referers = new ArrayList<>(ways.size()); 246 for (Node n: nodes) { 247 referers.clear(); 248 for (OsmPrimitive o: n.getReferrers()) { 249 if (ways.contains(o)) 250 referers.add((Way) o); 251 } 252 if (referers.size() == 1) { 253 Way way = referers.get(0); 254 if (way.isFirstLastNode(n)) continue; 255 cmds.add(lines.get(way).projectionCommand(n)); 256 } else if (referers.size() == 2) { 257 Command cmd = lines.get(referers.get(0)).intersectionCommand(n, lines.get(referers.get(1))); 258 cmds.add(cmd); 259 } else 260 throw new InvalidSelection(tr("Intersection of three or more ways can not be solved. Abort.")); 261 } 262 return new SequenceCommand(tr("Align Nodes in Line"), cmds); 263 } 264 265 /** 266 * Get lines useful to do alignment of a single node 267 * @param node Node to be aligned 268 * @param refWays Ways where useful lines will be searched 269 * @return List of useful lines 270 * @throws InvalidSelection if a node got more than 4 neighbours (self-crossing way) 271 */ 272 private static List<Line> getInvolvedLines(Node node, List<Way> refWays) throws InvalidSelection { 273 List<Line> lines = new ArrayList<>(); 274 List<Node> neighbors = new ArrayList<>(); 275 for (Way way: refWays) { 276 List<Node> nodes = way.getNodes(); 277 neighbors.clear(); 278 for (int i = 1; i < nodes.size()-1; i++) { 279 if (nodes.get(i) == node) { 280 neighbors.add(nodes.get(i-1)); 281 neighbors.add(nodes.get(i+1)); 282 } 283 } 284 if (neighbors.isEmpty()) 285 continue; 286 else if (neighbors.size() == 2) 287 // Non self crossing 288 lines.add(new Line(neighbors.get(0), neighbors.get(1))); 289 else if (neighbors.size() == 4) { 290 // Self crossing, have to make 2 lines with 4 neighbors 291 // see #9081 comment 6 292 EastNorth c = node.getEastNorth(); 293 double[] angle = new double[4]; 294 for (int i = 0; i < 4; i++) { 295 EastNorth p = neighbors.get(i).getEastNorth(); 296 angle[i] = Math.atan2(p.north() - c.north(), p.east() - c.east()); 297 } 298 double[] deltaAngle = new double[3]; 299 for (int i = 0; i < 3; i++) { 300 deltaAngle[i] = angle[i+1] - angle[0]; 301 if (deltaAngle[i] < 0) 302 deltaAngle[i] += 2*Math.PI; 303 } 304 int nb = 0; 305 if (deltaAngle[1] < deltaAngle[0]) nb++; 306 if (deltaAngle[2] < deltaAngle[0]) nb++; 307 if (nb == 1) { 308 // Align along [neighbors[0], neighbors[1]] and [neighbors[0], neighbors[2]] 309 lines.add(new Line(neighbors.get(0), neighbors.get(1))); 310 lines.add(new Line(neighbors.get(2), neighbors.get(3))); 311 } else { 312 // Align along [neighbors[0], neighbors[2]] and [neighbors[1], neighbors[3]] 313 lines.add(new Line(neighbors.get(0), neighbors.get(2))); 314 lines.add(new Line(neighbors.get(1), neighbors.get(3))); 315 } 316 } else 317 throw new InvalidSelection("cannot treat more than 4 neighbours, got "+neighbors.size()); 318 } 319 return lines; 320 } 321 322 /** 323 * Align a single node relative to a set of lines #9081 324 * @param node Node to be aligned 325 * @param lines Lines to align node on 326 * @return Command that perform action 327 * @throws InvalidSelection if more than 2 lines 328 */ 329 private static Command alignSingleNode(Node node, List<Line> lines) throws InvalidSelection { 330 if (lines.size() == 1) 331 return lines.get(0).projectionCommand(node); 332 else if (lines.size() == 2) 333 return lines.get(0).intersectionCommand(node, lines.get(1)); 334 throw new InvalidSelection(); 335 } 336 337 /** 338 * Class that represent a line 339 */ 340 private static class Line { 341 342 /** 343 * Line equation ax + by + c = 0 344 * Such as a^2 + b^2 = 1, ie (-b, a) is a unit vector of line 345 */ 346 private double a, b, c; 347 /** 348 * (xM, yM) are coordinates of a point of the line 349 */ 350 private double xM, yM; 351 352 /** 353 * Init a line by 2 nodes. 354 * @param first One point of the line 355 * @param last Other point of the line 356 * @throws InvalidSelection if nodes have same coordinates 357 */ 358 Line(Node first, Node last) throws InvalidSelection { 359 xM = first.getEastNorth().getX(); 360 yM = first.getEastNorth().getY(); 361 double xB = last.getEastNorth().getX(); 362 double yB = last.getEastNorth().getY(); 363 a = yB - yM; 364 b = xM - xB; 365 double norm = Math.sqrt(a*a + b*b); 366 if (norm == 0) 367 throw new InvalidSelection("Nodes have same coordinates!"); 368 a /= norm; 369 b /= norm; 370 c = -(a*xM + b*yM); 371 } 372 373 /** 374 * Init a line equation from a way. 375 * @param way Use extremity of this way to compute line equation 376 * @throws InvalidSelection if nodes have same coordinates 377 */ 378 Line(Way way) throws InvalidSelection { 379 this(way.firstNode(), way.lastNode()); 380 } 381 382 /** 383 * Orthogonal projection of a node N along this line. 384 * @param n Node to be projected 385 * @return The command that do the projection of this node 386 */ 387 public Command projectionCommand(Node n) { 388 double s = (xM - n.getEastNorth().getX()) * a + (yM - n.getEastNorth().getY()) * b; 389 return new MoveCommand(n, a*s, b*s); 390 } 391 392 /** 393 * Intersection of two line. 394 * @param n Node to move to the intersection 395 * @param other Second line for intersection 396 * @return The command that move the node 397 * @throws InvalidSelection if two parallels ways found 398 */ 399 public Command intersectionCommand(Node n, Line other) throws InvalidSelection { 400 double d = this.a * other.b - other.a * this.b; 401 if (Math.abs(d) < 10e-6) 402 // parallels lines 403 throw new InvalidSelection(tr("Two parallels ways found. Abort.")); 404 double x = (this.b * other.c - other.b * this.c) / d; 405 double y = (other.a * this.c - this.a * other.c) / d; 406 return new MoveCommand(n, x - n.getEastNorth().getX(), y - n.getEastNorth().getY()); 407 } 408 } 409 410 @Override 411 protected void updateEnabledState() { 412 setEnabled(getCurrentDataSet() != null && !getCurrentDataSet().getSelected().isEmpty()); 413 } 414 415 @Override 416 protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) { 417 setEnabled(selection != null && !selection.isEmpty()); 418 } 419}