Index: trunk/src/org/openstreetmap/josm/actions/AlignInRectangleAction.java =================================================================== --- trunk/src/org/openstreetmap/josm/actions/AlignInRectangleAction.java (revision 1075) +++ (revision ) @@ -1,136 +1,0 @@ -// License: GPL. See LICENSE file for details. -// -package org.openstreetmap.josm.actions; - -import static org.openstreetmap.josm.tools.I18n.tr; - -import java.awt.event.ActionEvent; -import java.awt.event.KeyEvent; -import java.util.Collection; -import java.util.LinkedList; - -import javax.swing.JOptionPane; - -import org.openstreetmap.josm.Main; -import org.openstreetmap.josm.command.Command; -import org.openstreetmap.josm.command.MoveCommand; -import org.openstreetmap.josm.command.SequenceCommand; -import org.openstreetmap.josm.data.coor.EastNorth; -import org.openstreetmap.josm.data.osm.Node; -import org.openstreetmap.josm.data.osm.OsmPrimitive; -import org.openstreetmap.josm.data.osm.Way; -import org.openstreetmap.josm.tools.ShortCut; - -/** - * Aligns all selected nodes within a rectangle. - * - * There are many ways this could be done, for example: - * - find smallest rectangle to contain all points (rectangular hull) OR - * - find largest rectangle to fit inside OR - * - find both and compute the average - * - * Also, it would be possible to let the user specify more input, e.g. - * two nodes that should remain where they are. - * - * This method uses the following algorithm: - * 1. compute "heading" of all four edges - * 2. select the edge that is oriented closest to the average of all headings - * @author Frederik Ramm - */ -public final class AlignInRectangleAction extends JosmAction { - - public AlignInRectangleAction() { - super(tr("Align Nodes in Rectangle"), "alignrect", tr("Move the selected nodes into a rectangle."), - ShortCut.registerShortCut("tools:alignrect", tr("Tool: {0}", tr("Align Nodes in Rectangle")), KeyEvent.VK_Q, ShortCut.GROUP_EDIT), true); - } - - public void actionPerformed(ActionEvent e) { - Collection sel = Main.ds.getSelected(); - Way myWay = null; - if (sel.size() == 1) - for (OsmPrimitive osm : sel) - if (osm instanceof Way) - myWay = (Way) osm; - - if ((myWay == null) || (myWay.nodes.size() != 5) || (!myWay.nodes.get(0).equals(myWay.nodes.get(4)))) { - JOptionPane.showMessageDialog(Main.parent, tr("Please select one circular way of exactly four nodes.")); - return; - } - - // find orientation of all four edges, compute average - double avg_angle = 0; - double angle[] = new double[4]; - EastNorth en[] = new EastNorth[5]; - for (int i=0; i<5; i++) en[i] = new EastNorth(myWay.nodes.get(i).eastNorth.east(), myWay.nodes.get(i).eastNorth.north()); - for (int i=0; i<4; i++) { - angle[i] = Math.asin((en[i+1].north()-en[i].north())/en[i+1].distance(en[i])) + 2 * Math.PI; - while(angle[i] > Math.PI/4) angle[i] -= Math.PI/2; - avg_angle += angle[i]; - } - avg_angle /= 4; - - // select edge that is closest to average, and use it as the base for the following - double best_dist = 0; - int base = 0; - for (int i=0; i<4; i++) - { - if ((i==0)||(Math.abs(angle[i]-avg_angle)) cmds = new LinkedList(); - for (int i=0; i<4; i++) { - Node n = myWay.nodes.get(i); - EastNorth ref = (i == base) ? begin : (i == (base+1)%4) ? end : (i==(base+2)%4) ? next : prev; - double dx = ref.east()-n.eastNorth.east(); - double dy = ref.north()-n.eastNorth.north(); - cmds.add(new MoveCommand(n, dx, dy)); - } - - Main.main.undoRedo.add(new SequenceCommand(tr("Align Nodes in Rectangle"), cmds)); - Main.map.repaint(); - } -} Index: trunk/src/org/openstreetmap/josm/actions/OrthogonalizeAction.java =================================================================== --- trunk/src/org/openstreetmap/josm/actions/OrthogonalizeAction.java (revision 1076) +++ trunk/src/org/openstreetmap/josm/actions/OrthogonalizeAction.java (revision 1076) @@ -0,0 +1,236 @@ +// License: GPL. See LICENSE file for details. +// +package org.openstreetmap.josm.actions; + +import static org.openstreetmap.josm.tools.I18n.tr; + +import java.awt.List; +import java.awt.event.ActionEvent; +import java.awt.event.KeyEvent; +import java.util.ArrayList; +import java.util.Collection; +import java.util.LinkedList; + +import javax.swing.JOptionPane; + +import org.openstreetmap.josm.Main; +import org.openstreetmap.josm.command.AddCommand; +import org.openstreetmap.josm.command.Command; +import org.openstreetmap.josm.command.MoveCommand; +import org.openstreetmap.josm.command.SequenceCommand; +import org.openstreetmap.josm.data.coor.EastNorth; +import org.openstreetmap.josm.data.coor.LatLon; +import org.openstreetmap.josm.data.osm.Node; +import org.openstreetmap.josm.data.osm.OsmPrimitive; +import org.openstreetmap.josm.data.osm.Way; +import org.openstreetmap.josm.tools.DontShowAgainInfo; +import org.openstreetmap.josm.tools.ShortCut; + +/** + * Align edges of a way so all angles are right angles. + * + * 1. Find orientation of all edges + * 2. Compute main orientation, weighted by length of edge, normalized to angles between 0 and pi/2 + * 3. Rotate every edge around its center to align with main orientation or perpendicular to it + * 4. Compute new intersection points of two adjascent edges + * 5. Move nodes to these points + */ +public final class OrthogonalizeAction extends JosmAction { + + public OrthogonalizeAction() { + super(tr("Orthogonalize shape"), + "ortho", + tr("Move nodes so all angles are 0/90/180/270deg"), + ShortCut.registerShortCut("tools:orthogonalize", tr("Tool: {0}", tr("Orthogonalize")), + KeyEvent.VK_Q, + ShortCut.GROUP_EDIT), true); + } + + public void actionPerformed(ActionEvent e) { + + Collection sel = Main.ds.getSelected(); + + ArrayList dirnodes = new ArrayList(); + + // Check the selection if it is suitible for the orthogonalization + for (OsmPrimitive osm : sel) { + // Check if not more than two nodes in the selection + if(osm instanceof Node) { + if(dirnodes.size() == 2) { + JOptionPane.showMessageDialog(Main.parent, tr("Only two nodes allowed")); + return; + } + dirnodes.add((Node) osm); + continue; + } + // Check if selection consists now only of ways + if (!(osm instanceof Way)) { + JOptionPane.showMessageDialog(Main.parent, tr("Selection must consist only of ways.")); + return; + } + + // Check if every way is made of at least four segments and closed + Way way = (Way)osm; + if ((way.nodes.size() < 5) || (!way.nodes.get(0).equals(way.nodes.get(way.nodes.size() - 1)))) { + JOptionPane.showMessageDialog(Main.parent, tr("Please select closed way(s) of at least four nodes.")); + return; + } + + // Check if every edge in the way is a definite edge of at least 45 degrees of direction change + // Otherwise, two segments could be turned into same direction and intersection would fail. + // Or changes of shape would be too serious. + for (int i1=0; i1 < way.nodes.size()-1; i1++) { + int i2 = (i1+1) % (way.nodes.size()-1); + int i3 = (i1+2) % (way.nodes.size()-1); + double angle1 =Math.abs(way.nodes.get(i1).eastNorth.heading(way.nodes.get(i2).eastNorth)); + double angle2 = Math.abs(way.nodes.get(i2).eastNorth.heading(way.nodes.get(i3).eastNorth)); + double delta = Math.abs(angle2 - angle1); + while(delta > Math.PI) delta -= Math.PI; + if(delta < Math.PI/4) { + JOptionPane.showMessageDialog(Main.parent, tr("Please select ways with almost right angles to orthogonalize.")); + return; + } + } + } + + if ("EPSG:4326".equals(Main.proj.toString())) { + String msg = tr("You are using the EPSG:4326 projection which might lead
" + + "to undesirable results when doing rectangular alignments.
" + + "Change your projection to get rid of this warning.
" + + "Do you want to continue?"); + + if (!DontShowAgainInfo.show("align_rectangular_4326", msg, false)) { + return; + } + } + // Check, if selection held neither none nor two nodes + if(dirnodes.size() == 1) { + JOptionPane.showMessageDialog(Main.parent, tr("Only one node selected")); + return; + } + + // Now all checks are done and we can now do the neccessary computations + // From here it is assumed that the above checks hold + Collection cmds = new LinkedList(); + double align_to_heading; + + + if(dirnodes.size() == 2) { // When selection contained two nodes, use the nodes to compute a direction to align to + double heading; + heading = dirnodes.get(0).eastNorth.heading(dirnodes.get(1).eastNorth); + while(heading > Math.PI/4) heading -= Math.PI/2; + align_to_heading=heading; + } else { // Otherwise compute the alignment direction from the ways in the collection + // First, compute the weighted average of the headings of all segments + double sum_weighted_headings = 0.0; + double sum_weights = 0.0; + for (OsmPrimitive osm : sel) { + if(!(osm instanceof Way)) + continue; + Way way = (Way)osm; + int nodes = way.nodes.size(); + int sides = nodes - 1; + // To find orientation of all segments, compute weighted average of all segment's headings + // all headings are mapped into [0, 3*4*PI) by PI/2 rotations so both main orientations are mapped into one + // the headings are weighted by the length of the segment establishing it, so a longer segment, that is more + // likely to have the correct orientation, has more influence in the computing than a short segment, that is easier to misalign. + for (int i=0; i < sides; i++) { + double heading; + double weight; + heading = way.nodes.get(i).eastNorth.heading(way.nodes.get(i+1).eastNorth); + //Put into [0, PI/4) to find main direction + while(heading > Math.PI/4) heading -= Math.PI/2; + weight = way.nodes.get(i).eastNorth.distance(way.nodes.get(i+1).eastNorth); + sum_weighted_headings += heading*weight; + sum_weights += weight; + } + } + align_to_heading = sum_weighted_headings/sum_weights; + } + + for (OsmPrimitive osm : sel) { + if(!(osm instanceof Way)) + continue; + Way myWay = (Way)osm; + int nodes = myWay.nodes.size(); + int sides = nodes - 1; + + // Copy necessary data into a more suitable data structure + EastNorth en[] = new EastNorth[sides]; + for (int i=0; i < sides; i++) { + en[i] = new EastNorth(myWay.nodes.get(i).eastNorth.east(), myWay.nodes.get(i).eastNorth.north()); + } + + for (int i=0; i < sides; i++) { + // Compute handy indices of three nodes to be used in one loop iteration. + // We use segments (i1,i2) and (i2,i3), align them and compute the new + // position of the i2-node as the intersection of the realigned (i1,i2), (i2,i3) segments + // Not the most efficient algorithm, but we don't handle millions of nodes... + int i1 = i; + int i2 = (i+1)%sides; + int i3 = (i+2)%sides; + double heading1, heading2; + double delta1, delta2; + // Compute neccessary rotation of first segment to align it with main orientation + heading1 = en[i1].heading(en[i2]); + //Put into [-PI/4, PI/4) because we want a minimum of rotation so we don't swap node positions + while(heading1 - align_to_heading > Math.PI/4) heading1 -= Math.PI/2; + while(heading1 - align_to_heading < -Math.PI/4) heading1 += Math.PI/2; + delta1 = align_to_heading - heading1; + // Compute neccessary rotation of second segment to align it with main orientation + heading2 = en[i2].heading(en[i3]); + //Put into [-PI/4, PI/4) because we want a minimum of rotation so we don't swap node positions + while(heading2 - align_to_heading > Math.PI/4) heading2 -= Math.PI/2; + while(heading2 - align_to_heading < -Math.PI/4) heading2 += Math.PI/2; + delta2 = align_to_heading - heading2; + // To align a segment, rotate around its center + EastNorth pivot1 = new EastNorth((en[i1].east()+en[i2].east())/2, (en[i1].north()+en[i2].north())/2); + EastNorth A=en[i1].rotate(pivot1, delta1); + EastNorth B=en[i2].rotate(pivot1, delta1); + EastNorth pivot2 = new EastNorth((en[i2].east()+en[i3].east())/2, (en[i2].north()+en[i3].north())/2); + EastNorth C=en[i2].rotate(pivot2, delta2); + EastNorth D=en[i3].rotate(pivot2, delta2); + + // compute intersection of segments + double u=det(B.east() - A.east(), B.north() - A.north(), + C.east() - D.east(), C.north() - D.north()); + + // Check for parallel segments and do nothing if they are + // In practice this will probably only happen when a way has + // been duplicated + + if (u == 0) continue; + + // q is a number between 0 and 1 + // It is the point in the segment where the intersection occurs + // if the segment is scaled to length 1 + + double q = det(B.north() - C.north(), B.east() - C.east(), + D.north() - C.north(), D.east() - C.east()) / u; + EastNorth intersection = new EastNorth( + B.east() + q * (A.east() - B.east()), + B.north() + q * (A.north() - B.north())); + + Node n = myWay.nodes.get(i2); + + LatLon ill = Main.proj.eastNorth2latlon(intersection); + if (!ill.equalsEpsilon(n.coor)) { + double dx = intersection.east()-n.eastNorth.east(); + double dy = intersection.north()-n.eastNorth.north(); + cmds.add(new MoveCommand(n, dx, dy)); + } + } + } + + if (cmds.size() > 0) { + Main.main.undoRedo.add(new SequenceCommand(tr("Orthogonalize"), cmds)); + Main.map.repaint(); + } + } + + static double det(double a, double b, double c, double d) + { + return a * d - b * c; + } + +} Index: trunk/src/org/openstreetmap/josm/data/coor/EastNorth.java =================================================================== --- trunk/src/org/openstreetmap/josm/data/coor/EastNorth.java (revision 1075) +++ trunk/src/org/openstreetmap/josm/data/coor/EastNorth.java (revision 1076) @@ -28,9 +28,53 @@ public EastNorth interpolate(EastNorth en2, double proportion) { - return new EastNorth(this.x + proportion * (en2.x - this.x),this.y + proportion * (en2.y - this.y)); + return new EastNorth(this.x + proportion * (en2.x - this.x), + this.y + proportion * (en2.y - this.y)); } + + /** + * Returns the heading, in radians, that you have to use to get from + * this EastNorth to another. Heading is mapped into [0, 2pi) + * + * @param other the "destination" position + * @return heading + */ + public double heading(EastNorth other) { + double hd = Math.atan2(other.east() - east(), other.north() - north()); + if(hd < 0) hd = 2 * Math.PI + hd; + return hd; + } + + public EastNorth sub(EastNorth en) { + return new EastNorth(en.east() - east(), en.north() - north()); + } + + /** + * Returns an EastNorth representing the this EastNorth rotatedaround + * a given EastNorth by a given angle + * @param pivot the center of the rotation + * @param angle the angle of the rotation + * @return EastNorth rotated object + */ + public EastNorth rotate(EastNorth pivot, double angle) { + double cosPhi = Math.cos(angle); + double sinPhi = Math.sin(angle); + double x = east() - pivot.east(); + double y = north() - pivot.north(); + double nx = cosPhi * x + sinPhi * y + pivot.east(); + double ny = -sinPhi * x + cosPhi * y + pivot.north(); + return new EastNorth(nx, ny); + } @Override public String toString() { return "EastNorth[e="+x+", n="+y+"]"; } + + /** + * Compares two EastNorth values + * + * @return true if "x" and "y" values are within 1E-6 of each other + */ + public boolean equalsEpsilon(EastNorth other, double e) { + return (Math.abs(x - other.x) < e && Math.abs(y - other.y) < e); + } } Index: trunk/src/org/openstreetmap/josm/gui/MainMenu.java =================================================================== --- trunk/src/org/openstreetmap/josm/gui/MainMenu.java (revision 1075) +++ trunk/src/org/openstreetmap/josm/gui/MainMenu.java (revision 1076) @@ -19,5 +19,5 @@ import org.openstreetmap.josm.actions.AlignInCircleAction; import org.openstreetmap.josm.actions.AlignInLineAction; -import org.openstreetmap.josm.actions.AlignInRectangleAction; +import org.openstreetmap.josm.actions.OrthogonalizeAction; import org.openstreetmap.josm.actions.AutoScaleAction; import org.openstreetmap.josm.actions.CombineWayAction; @@ -106,5 +106,5 @@ public final JosmAction alignInCircle = new AlignInCircleAction(); public final JosmAction alignInLine = new AlignInLineAction(); - public final JosmAction alignInRect = new AlignInRectangleAction(); + public final JosmAction ortho = new OrthogonalizeAction(); public final JosmAction createCircle = new CreateCircleAction(); public final JosmAction mergeNodes = new MergeNodesAction(); @@ -223,5 +223,5 @@ add(toolsMenu, alignInCircle); add(toolsMenu, alignInLine); - add(toolsMenu, alignInRect); + add(toolsMenu, ortho); toolsMenu.addSeparator(); add(toolsMenu, createCircle);