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