Index: trunk/src/org/openstreetmap/josm/actions/OrthogonalizeAction.java =================================================================== --- trunk/src/org/openstreetmap/josm/actions/OrthogonalizeAction.java (revision 1087) +++ trunk/src/org/openstreetmap/josm/actions/OrthogonalizeAction.java (revision 1089) @@ -47,12 +47,12 @@ } - public void actionPerformed(ActionEvent e) { - - Collection sel = Main.ds.getSelected(); - + 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) { + for (OsmPrimitive osm : sel) { // Check if not more than two nodes in the selection if(osm instanceof Node) { @@ -65,9 +65,9 @@ } // Check if selection consists now only of ways - if (!(osm instanceof Way)) { + if (!(osm instanceof Way)) { JOptionPane.showMessageDialog(Main.parent, tr("Selection must consist only of ways.")); - return; + return; } - + // Check if every way is made of at least four segments and closed Way way = (Way)osm; @@ -76,19 +76,19 @@ 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; - } + 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; + } } } @@ -96,7 +96,7 @@ 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?"); + "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)) { @@ -108,58 +108,83 @@ 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; + double align_to_heading = 0.0; + boolean use_dirnodes = false; + + if(dirnodes.size() == 2) { + // When selection contains two nodes, use the nodes to compute a direction + // to align all ways to + align_to_heading = normalize_angle(dirnodes.get(0).eastNorth.heading(dirnodes.get(1).eastNorth)); + use_dirnodes = true; + } + for (OsmPrimitive osm : sel) { - if(!(osm instanceof Way)) - continue; + 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++) { + en[i] = new EastNorth(way.nodes.get(i).eastNorth.east(), way.nodes.get(i).eastNorth.north()); + } + + if (! use_dirnodes) { + // To find orientation of all segments, compute weighted average of all segment's headings + // all headings are mapped into [-PI/4, PI/4] 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. + double headings[] = new double[sides]; + double weights[] = new double[sides]; + for (int i=0; i < sides; i++) { + headings[i] = normalize_angle(way.nodes.get(i).eastNorth.heading(way.nodes.get(i+1).eastNorth)); + weights[i] = way.nodes.get(i).eastNorth.distance(way.nodes.get(i+1).eastNorth); + } + + // CAVEAT: for orientations near -PI/4 or PI/4 the mapping into ONE orientation fails + // resulting in a heading-difference between adjacent sides of almost PI/2 + // and a totally wrong average + // check for this (use PI/3 as arbitray limit) and rotate into ONE orientation + double angle_diff_max = 0.0; + for (int i=0; i < sides; i++) { + double diff = 0.0; + if (i == 0) { + diff = heading_diff(headings[i], headings[sides - 1]); + } else { + diff = heading_diff(headings[i], headings[i - 1]); + } + if (diff > angle_diff_max) angle_diff_max = diff; + } + + if (angle_diff_max > Math.PI/3) { + // rearrange headings: everything < 0 gets PI/2-rotated + for (int i=0; i < sides; i++) { + if (headings[i] < 0) + headings[i] += Math.PI/2; + } + } + + // TODO: + // use angle_diff_max as an indicator that the way is already orthogonal + // e.g. if angle_diff_max is less then Math.toRadians(0.5) + // and do nothing in that case (?) + + // Compute the weighted average of the headings of all segments + double sum_weighted_headings = 0.0; + double sum_weights = 0.0; + for (int i=0; i < sides; i++) { + sum_weighted_headings += headings[i] * weights[i]; + sum_weights += weights[i]; + } + align_to_heading = normalize_angle(sum_weighted_headings/sum_weights); + } + + for (int i=0; i < sides; i++) { // Compute handy indices of three nodes to be used in one loop iteration. @@ -173,14 +198,8 @@ 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; + heading1 = normalize_angle(en[i1].heading(en[i2]), align_to_heading); 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; + heading2 = normalize_angle(en[i2].heading(en[i3]), align_to_heading); delta2 = align_to_heading - heading2; // To align a segment, rotate around its center @@ -194,23 +213,23 @@ // compute intersection of segments double u=det(B.east() - A.east(), B.north() - A.north(), - C.east() - D.east(), C.north() - D.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; + 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); + + Node n = way.nodes.get(i2); LatLon ill = Main.proj.eastNorth2latlon(intersection); @@ -218,15 +237,15 @@ double dx = intersection.east()-n.eastNorth.east(); double dy = intersection.north()-n.eastNorth.north(); - cmds.add(new MoveCommand(n, dx, dy)); - } - } - } - + 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) { @@ -234,3 +253,19 @@ } + static double normalize_angle(double h) { + return normalize_angle(h, 0.0); + } + static double normalize_angle(double h, double align_to) { + double llimit = -Math.PI/4; + double ulimit = Math.PI/4; + while (h - align_to > ulimit) h -= Math.PI/2; + while (h - align_to < llimit) h += Math.PI/2; + + return h; + } + + static double heading_diff(double h1, double h2) { + double heading_delta = h1 > h2 ? h1 - h2 : h2 - h1; + return heading_delta; + } }