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