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