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