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