Changeset 2268 in josm


Ignore:
Timestamp:
2009-10-10T20:33:54+02:00 (15 years ago)
Author:
stoecker
Message:

fix #3571 - patch by bastiK - improve orthogonalization action

Location:
trunk/src/org/openstreetmap/josm
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/org/openstreetmap/josm/actions/OrthogonalizeAction.java

    r2256 r2268  
    88import java.awt.event.KeyEvent;
    99import java.util.ArrayList;
     10import java.util.Arrays;
    1011import java.util.Collection;
     12import java.util.HashSet;
     13import java.util.HashMap;
    1114import java.util.LinkedList;
    1215
     
    2629
    2730/**
    28  * Align edges of a way so all angles are right angles.
     31 * Tools / Orthogonalize
    2932 *
    30  * 1. Find orientation of all edges
    31  * 2. Compute main orientation, weighted by length of edge, normalized to angles between 0 and pi/2
    32  * 3. Rotate every edge around its center to align with main orientation or perpendicular to it
    33  * 4. Compute new intersection points of two adjascent edges
    34  * 5. Move nodes to these points
    35  * 6. if there are nodes between edges then align the nodes
     33 * Align edges of a way so all angles are angles of 90 or 180 degrees.
     34 * See USAGE String below.
    3635 */
    3736public final class OrthogonalizeAction extends JosmAction {
     37    String USAGE = "<h3>"+
     38            "When one or more ways are selected, the shape is adjusted, such that all angles are 90 or 180 degrees.<h3>"+
     39            "You can add two nodes to the selection. Then the direction is fixed by these two reference nodes.<h3>"+
     40            "(Afterwards, you can undo the movement for certain nodes:<br>"+
     41            "Select them and press the shortcut for Orthogonalize / Undo. The default is Shift-Q.)";
    3842
    3943    public OrthogonalizeAction() {
     
    4650    }
    4751
     52    /**
     53     * excepted deviation from an angle of 0, 90, 180, 360 degrees
     54     * maximum value: 45 degrees
     55     */
     56    private static final double TOLERANCE1 = Math.toRadians(35.);   // within a way
     57    private static final double TOLERANCE2 = Math.toRadians(35.);   // ways relative to each other
     58
     59    /**
     60     * Remember movements, so the user can later undo it for certain nodes
     61     */
     62    private static final HashMap<Node, EastNorth> rememberMovements = new HashMap<Node, EastNorth>();
     63
     64    /**
     65     * Undo the previous orthogonalization for certain nodes.
     66     *
     67     * This is useful, if the way shares nodes that you don't like to change, e.g. imports or
     68     * work of another user.
     69     *
     70     * This action can be triggered by shortcut only.
     71     */
     72    public class Undo extends JosmAction {
     73        public Undo() {
     74            super(tr("Orthogonalize Shape / Undo"),
     75                "ortho",
     76                tr("Undo orthogonalization for certain nodes"),
     77                Shortcut.registerShortcut("tools:orthogonalizeUndo", tr("Tool: {0}", tr("Orthogonalize Shape / Undo")),
     78                        KeyEvent.VK_Q,
     79                        Shortcut.GROUP_EDIT, Shortcut.SHIFT_DEFAULT), true);
     80        }
     81        public void actionPerformed(ActionEvent e) {
     82            if (!isEnabled())
     83                return;
     84            final Collection<Command> commands = new LinkedList<Command>();
     85            final Collection<OsmPrimitive> sel = getCurrentDataSet().getSelected();
     86            try {
     87                for (OsmPrimitive p : sel) {
     88                    if (! (p instanceof Node)) throw new InvalidUserInputException();
     89                    Node n = (Node) p;
     90                    if (rememberMovements.containsKey(n)) {
     91                        EastNorth tmp = rememberMovements.get(n);
     92                        commands.add(new MoveCommand(n, - tmp.east(), - tmp.north()));
     93                        rememberMovements.remove(n);
     94                    }
     95                }
     96                if (commands.size() > 0) {
     97                    Main.main.undoRedo.add(new SequenceCommand(tr("Orthogonalize / Undo"), commands));
     98                    Main.map.repaint();
     99                } else throw new InvalidUserInputException();
     100            }
     101            catch (InvalidUserInputException ex) {
     102                JOptionPane.showMessageDialog(
     103                    Main.parent,
     104                    tr("Orthogonalize Shape / Undo\n"+
     105                        "Please select nodes that were moved by the previous Orthogonalize Shape action!"),
     106                    tr("Undo Orthogonalize Shape"),
     107                    JOptionPane.INFORMATION_MESSAGE);
     108            }
     109        }
     110    }
     111
    48112    public void actionPerformed(ActionEvent e) {
    49113        if (!isEnabled())
    50114            return;
    51         Collection<OsmPrimitive> sel = getCurrentDataSet().getSelected();
    52 
    53         ArrayList<Node> dirnodes = new ArrayList<Node>();
    54         ArrayList<Node> alignNodes = new ArrayList<Node>();
    55 
    56         // Check the selection if it is suitable for the orthogonalisation
    57         for (OsmPrimitive osm : sel) {
    58             // Check if not more than two nodes in the selection
    59             if(osm instanceof Node) {
    60                 if(dirnodes.size() == 2) {
    61                     JOptionPane.showMessageDialog(
    62                             Main.parent,
    63                             tr("Only two nodes allowed"),
    64                             tr("Information"),
    65                             JOptionPane.INFORMATION_MESSAGE
    66                     );
    67                     return;
    68                 }
    69                 dirnodes.add((Node) osm);
    70                 continue;
    71             }
    72             // Check if selection consists now only of ways
    73             if (!(osm instanceof Way)) {
    74                 JOptionPane.showMessageDialog(
    75                         Main.parent,
    76                         tr("Selection must consist only of ways."),
    77                         tr("Information"),
    78                         JOptionPane.INFORMATION_MESSAGE
    79                 );
    80                 return;
    81             }
    82 
    83             // Check if every way is made of at least four segments and closed
    84             Way way = (Way)osm;
    85             if ((way.getNodesCount() < 5) || !way.isClosed()) {
    86                 JOptionPane.showMessageDialog(
    87                         Main.parent,
    88                         tr("Please select one or more closed ways of at least four nodes."),
    89                         tr("Information"),
    90                         JOptionPane.INFORMATION_MESSAGE
    91                 );
    92                 return;
    93             }
    94 
    95             // Check if every edge in the way is a definite edge of at least 45 degrees of direction change
    96             // Otherwise, two segments could be turned into same direction and intersection would fail.
    97             // Or changes of shape would be too serious.
    98             for (int i1=0; i1 < way.getNodesCount()-1; i1++) {
    99                 int i2 = (i1+1) % (way.getNodesCount()-1);
    100                 int i3 = (i1+2) % (way.getNodesCount()-1);
    101                 double angle1  =Math.abs(way.getNode(i1).getEastNorth().heading(way.getNode(i2).getEastNorth()));
    102                 double angle2 = Math.abs(way.getNode(i2).getEastNorth().heading(way.getNode(i3).getEastNorth()));
    103                 double delta = Math.abs(angle2 - angle1);
    104                 while(delta > Math.PI) {
    105                     delta -= Math.PI;
    106                 }
    107                 if(delta < Math.PI/4) {
    108                     // not an edge
    109                     alignNodes.add(way.getNode(i2));
    110                 }
    111             }
    112 
    113             // first node has to be an edge so we move the node to the end of the way
    114             while (alignNodes.contains(way.firstNode())) {
    115                 Node n = way.firstNode();
    116                 way.removeNode(n);
    117                 way.addNode(way.getNodesCount() - 2, n); // ! -2 because first node == last node in closed way
    118             }
    119         }
    120 
    121115        if ("EPSG:4326".equals(Main.proj.toString())) {
    122116            String msg = tr("<html>You are using the EPSG:4326 projection which might lead<br>" +
     
    134128                return;
    135129        }
    136         // Check, if selection held neither none nor two nodes
    137         if(dirnodes.size() == 1) {
    138             JOptionPane.showMessageDialog(
     130
     131        final ArrayList<Node> nodeList = new ArrayList<Node>();
     132        final ArrayList<WayData> wayDataList = new ArrayList<WayData>();
     133        final Collection<OsmPrimitive> sel = getCurrentDataSet().getSelected();
     134
     135        try {
     136            // collect nodes and ways from the selection
     137            for (OsmPrimitive p : sel) {
     138                if (p instanceof Node) {
     139                    nodeList.add((Node) p);
     140                }
     141                else if (p instanceof Way) {
     142                    wayDataList.add(new WayData((Way) p));
     143                }
     144                else {      // maybe a relation got selected...
     145                    throw new InvalidUserInputException("Selection must consist only of ways and nodes.");
     146                }
     147            }
     148            if (wayDataList.isEmpty()) {
     149                throw new InvalidUserInputException("usage");
     150            }
     151            else  {
     152                if (nodeList.size() == 2) {
     153                    orthogonalize(wayDataList, nodeList);
     154                }
     155                else if (nodeList.isEmpty()) {
     156                    orthogonalize(wayDataList, nodeList);
     157                }
     158                else {
     159                    throw new InvalidUserInputException("usage");
     160                }
     161            }
     162        } catch (InvalidUserInputException ex) {
     163            if (ex.getMessage().equals("usage")) {
     164                JOptionPane.showMessageDialog(
    139165                    Main.parent,
    140                     tr("Only one node selected"),
    141                     tr("Warning"),
    142                     JOptionPane.WARNING_MESSAGE
    143             );
    144             return;
    145         }
    146 
    147         // Now all checks are done and we can now do the neccessary computations
    148         // From here it is assumed that the above checks hold
    149         Collection<Command> cmds = new LinkedList<Command>();
    150         double align_to_heading = 0.0;
    151         boolean use_dirnodes = false;
    152 
    153         if (dirnodes.size() == 2) {
    154             // When selection contains two nodes, use the nodes to compute a direction
    155             // to align all ways to
    156             align_to_heading = normalize_angle(dirnodes.get(0).getEastNorth().heading(dirnodes.get(1).getEastNorth()));
    157             use_dirnodes = true;
    158         }
    159 
    160         for (OsmPrimitive osm : sel) {
    161             if(!(osm instanceof Way)) {
    162                 continue;
    163             }
    164 
    165             Way oldWay = (Way) osm;
    166             Way way = new Way();
    167             // copy only edges into way
    168             for (Node origNode : oldWay.getNodes()) {
    169                 if (alignNodes.contains(origNode)) {
    170                     continue;
    171                 }
    172                 way.addNode(origNode);
    173             }
    174             int nodes = way.getNodesCount();
    175             int sides = nodes - 1;
    176             // Copy necessary data into a more suitable data structure
    177             EastNorth en[] = new EastNorth[sides];
    178             for (int i = 0; i < sides; i++) {
    179                 en[i] = new EastNorth(way.getNode(i).getEastNorth().east(), way.getNode(i).getEastNorth().north());
    180             }
    181 
    182             if (! use_dirnodes) {
    183                 // To find orientation of all segments, compute weighted average of all segment's headings
    184                 // all headings are mapped into [-PI/4, PI/4] by PI/2 rotations so both main orientations are mapped into one
    185                 // the headings are weighted by the length of the segment establishing it, so a longer segment, that is more
    186                 // likely to have the correct orientation, has more influence in the computing than a short segment, that is easier to misalign.
    187                 double headings[] = new double[sides];
    188                 double weights[] = new double[sides];
    189                 for (int i=0; i < sides; i++) {
    190                     headings[i] = normalize_angle(way.getNode(i).getEastNorth().heading(way.getNode(i+1).getEastNorth()));
    191                     weights[i] = way.getNode(i).getEastNorth().distance(way.getNode(i+1).getEastNorth());
    192                 }
    193 
    194                 // CAVEAT: for orientations near -PI/4 or PI/4 the mapping into ONE orientation fails
    195                 //         resulting in a heading-difference between adjacent sides of almost PI/2
    196                 //         and a totally wrong average
    197                 // check for this (use PI/3 as arbitray limit) and rotate into ONE orientation
    198                 double angle_diff_max = 0.0;
    199                 for (int i=0; i < sides; i++) {
    200                     double diff = 0.0;
    201                     if (i == 0) {
    202                         diff = heading_diff(headings[i], headings[sides - 1]);
    203                     } else {
    204                         diff = heading_diff(headings[i], headings[i - 1]);
    205                     }
    206                     if (diff > angle_diff_max) {
    207                         angle_diff_max = diff;
    208                     }
    209                 }
    210 
    211                 if (angle_diff_max > Math.PI/3) {
    212                     // rearrange headings: everything < 0 gets PI/2-rotated
    213                     for (int i=0; i < sides; i++) {
    214                         if (headings[i] < 0) {
    215                             headings[i] += Math.PI/2;
     166                    "<html><h2>"+tr("Usage")+tr(USAGE),
     167                    tr("Orthogonalize Shape"),
     168                    JOptionPane.INFORMATION_MESSAGE);
     169            }
     170            else {
     171                JOptionPane.showMessageDialog(
     172                    Main.parent,
     173                    "<html><h3>"+tr(ex.getMessage())+"<br><hr><h3>"+tr("Usage")+tr(USAGE),
     174                    tr("Selected Elements cannot be orthogonalized"),
     175                    JOptionPane.INFORMATION_MESSAGE);
     176            }
     177        }
     178    }
     179
     180    /**
     181     *
     182     *  Outline:
     183     *  1. Find direction of all segments
     184     *      - direction = 0..3 (right,up,left,down)
     185     *      - right is not really right, you may have to turn your screen
     186     *  2. Find average heading of all segments
     187     *      - heading = angle of a vector in polar coordinates
     188     *      - sum up horizontal segments (those with direction 0 or 2)
     189     *      - sum up vertical segments
     190     *      - turn the vertical sum by 90 degrees and add it to the horizontal sum
     191     *      - get the average heading from this total sum
     192     *  3. Rotate all nodes by the average heading so that right is really right
     193     *      and all segments are approximately NS or EW.
     194     *  4. If nodes are connected by a horizontal segment: Replace their y-Coordinate by
     195     *      the mean value of their y-Coordinates.
     196     *      - The same for vertical segments.
     197     *  5. Rotate back.
     198     *
     199     **/
     200    private static void orthogonalize(ArrayList<WayData> wayDataList, ArrayList<Node> headingNodes)
     201        throws InvalidUserInputException
     202    {
     203        // find average heading
     204        double headingAll;
     205        try {
     206            if (headingNodes.isEmpty()) {
     207                // find directions of the segments and make them consistent between different ways
     208                wayDataList.get(0).calcDirections(Direction.RIGHT);
     209                double refHeading = wayDataList.get(0).heading;
     210                for (WayData w : wayDataList) {
     211                    w.calcDirections(Direction.RIGHT);
     212                    int directionOffset = angleToDirectionChange(w.heading - refHeading, TOLERANCE2);
     213                    w.calcDirections(Direction.RIGHT.changeBy(directionOffset));
     214                    if (angleToDirectionChange(refHeading - w.heading, TOLERANCE2) != 0) throw new RuntimeException();
     215                }
     216                EastNorth totSum = new EastNorth(0., 0.);
     217                for (WayData w : wayDataList) {
     218                    totSum = EN.sum(totSum, w.segSum);
     219                }
     220                headingAll = EN.polar(new EastNorth(0., 0.), totSum);
     221            }
     222            else {
     223                headingAll = EN.polar(headingNodes.get(0).getEastNorth(), headingNodes.get(1).getEastNorth());
     224                for (WayData w : wayDataList) {
     225                    w.calcDirections(Direction.RIGHT);
     226                    int directionOffset = angleToDirectionChange(w.heading - headingAll, TOLERANCE2);
     227                    w.calcDirections(Direction.RIGHT.changeBy(directionOffset));
     228                }
     229            }
     230        } catch (RejectedAngleException ex) {
     231            throw new InvalidUserInputException(
     232                "<html>Please make sure all selected ways head in a similar direction<br>"+
     233                "or orthogonalize them one by one.");
     234        }
     235
     236        // put the nodes of all ways in a set
     237        final HashSet<Node> allNodes = new HashSet<Node>();
     238        for (WayData w : wayDataList) {
     239            for (Node n : w.way.getNodes()) {
     240                allNodes.add(n);
     241            }
     242        }
     243
     244        // the new x and y value for each node
     245        final HashMap<Node, Double> nX = new HashMap<Node, Double>();
     246        final HashMap<Node, Double> nY = new HashMap<Node, Double>();
     247
     248        // caluclate the centroid of all nodes
     249        // it is used as rotation center
     250        EastNorth pivot = new EastNorth(0., 0.);
     251        for (Node n : allNodes) {
     252            pivot = EN.sum(pivot, n.getEastNorth());
     253        }
     254        pivot = new EastNorth(pivot.east() / allNodes.size(), pivot.north() / allNodes.size());
     255
     256        // rotate
     257        for (Node n: allNodes) {
     258            EastNorth tmp = EN.rotate_cc(pivot, n.getEastNorth(), - headingAll);
     259            nX.put(n, tmp.east());
     260            nY.put(n, tmp.north());
     261        }
     262
     263        // orthogonalize
     264        final Direction[] HORIZONTAL = {Direction.RIGHT, Direction.LEFT};
     265        final Direction[] VERTICAL = {Direction.UP, Direction.DOWN};
     266        final Direction[][] ORIENTATIONS = {HORIZONTAL, VERTICAL};
     267        for (Direction[] orientation : ORIENTATIONS){
     268            final HashSet<Node> s = new HashSet<Node>(allNodes);
     269            int s_size = s.size();
     270            for (int dummy = 0; dummy < s_size; ++ dummy) {     
     271                if (s.isEmpty()) break;                         
     272                final Node dummy_n = s.iterator().next();     // pick arbitrary element of s
     273
     274                final HashSet<Node> cs = new HashSet<Node>(); // will contain each node that can be reached from dummy_n
     275                cs.add(dummy_n);                              // walking only on horizontal / vertical segments
     276
     277                boolean somethingHappened = true;
     278                while (somethingHappened) {
     279                    somethingHappened = false;
     280                    for (WayData w : wayDataList) {
     281                        for (int i=0; i < w.nSeg; ++i) {
     282                            Node n1 = w.way.getNodes().get(i);
     283                            Node n2 = w.way.getNodes().get(i+1);
     284                            if (Arrays.asList(orientation).contains(w.segDirections[i])) {
     285                                if (cs.contains(n1) && ! cs.contains(n2)) {
     286                                    cs.add(n2);
     287                                    somethingHappened = true;
     288                                }
     289                                if (cs.contains(n2) && ! cs.contains(n1)) {
     290                                    cs.add(n1);
     291                                    somethingHappened = true;
     292                                }
     293                            }
    216294                        }
    217295                    }
    218296                }
    219297
    220                 // TODO:
    221                 // use angle_diff_max as an indicator that the way is already orthogonal
    222                 // e.g. if angle_diff_max is less then Math.toRadians(0.5)
    223                 // and do nothing in that case (?)
    224 
    225                 // Compute the weighted average of the headings of all segments
    226                 double sum_weighted_headings = 0.0;
    227                 double sum_weights = 0.0;
    228                 for (int i=0; i < sides; i++) {
    229                     sum_weighted_headings += headings[i] * weights[i];
    230                     sum_weights += weights[i];
    231                 }
    232                 align_to_heading = normalize_angle(sum_weighted_headings/sum_weights);
    233             }
    234 
    235             EastNorth aligna = null;
    236             EastNorth alignb = null;
    237             EastNorth align0 = null;
    238             Node nodea = null;
    239             Node nodeb = null;
    240             Node node0 = null;
    241 
    242             for (int i=0; i < sides; i++) {
    243                 // Compute handy indices of three nodes to be used in one loop iteration.
    244                 // We use segments (i1,i2) and (i2,i3), align them and compute the new
    245                 // position of the i2-node as the intersection of the realigned (i1,i2), (i2,i3) segments
    246                 // Not the most efficient algorithm, but we don't handle millions of nodes...
    247                 int i1 = i;
    248                 int i2 = (i+1)%sides;
    249                 int i3 = (i+2)%sides;
    250                 double heading1, heading2;
    251                 double delta1, delta2;
    252                 // Compute neccessary rotation of first segment to align it with main orientation
    253                 heading1 = normalize_angle(en[i1].heading(en[i2]), align_to_heading);
    254                 delta1 = align_to_heading - heading1;
    255                 // Compute neccessary rotation of second segment to align it with main orientation
    256                 heading2 = normalize_angle(en[i2].heading(en[i3]), align_to_heading);
    257                 delta2 = align_to_heading - heading2;
    258                 // To align a segment, rotate around its center
    259                 EastNorth pivot1 = new EastNorth((en[i1].east()+en[i2].east())/2, (en[i1].north()+en[i2].north())/2);
    260                 EastNorth A=en[i1].rotate(pivot1, delta1);
    261                 EastNorth B=en[i2].rotate(pivot1, delta1);
    262                 EastNorth pivot2 = new EastNorth((en[i2].east()+en[i3].east())/2, (en[i2].north()+en[i3].north())/2);
    263                 EastNorth C=en[i2].rotate(pivot2, delta2);
    264                 EastNorth D=en[i3].rotate(pivot2, delta2);
    265 
    266                 // compute intersection of segments
    267                 double u=det(B.east() - A.east(), B.north() - A.north(),
    268                         C.east() - D.east(), C.north() - D.north());
    269 
    270                 // Check for parallel segments and do nothing if they are
    271                 // In practice this will probably only happen when a way has
    272                 // been duplicated
    273 
    274                 if (u == 0) {
    275                     continue;
    276                 }
    277 
    278                 // q is a number between 0 and 1
    279                 // It is the point in the segment where the intersection occurs
    280                 // if the segment is scaled to length 1
    281 
    282                 double q = det(B.north() - C.north(), B.east() - C.east(),
    283                         D.north() - C.north(), D.east() - C.east()) / u;
    284                 EastNorth intersection = new EastNorth(
    285                         B.east() + q * (A.east() - B.east()),
    286                         B.north() + q * (A.north() - B.north()));
    287 
    288                 Node n = way.getNode(i2);
    289 
    290                 LatLon ill = Main.proj.eastNorth2latlon(intersection);
    291                 if (!ill.equalsEpsilon(n.getCoor())) {
    292                     double dx = intersection.east()-n.getEastNorth().east();
    293                     double dy = intersection.north()-n.getEastNorth().north();
    294                     cmds.add(new MoveCommand(n, dx, dy));
    295                 }
    296 
    297                 // align all nodes between two edges
    298                 aligna = alignb;
    299                 alignb = intersection;
    300                 nodea = nodeb;
    301                 nodeb = n;
    302                 if (aligna != null) {
    303 
    304                     MoveCommand cmd = alignSide(findNodesToAlign(oldWay, nodea, nodeb), aligna, alignb);
    305                     if (cmd != null) {
    306                         cmds.add(cmd);
     298                final HashMap<Node, Double> nC = (orientation == HORIZONTAL) ? nY : nX;
     299
     300                double average = 0;
     301                for (Node n : cs) {
     302                    average += nC.get(n).doubleValue();
     303                }
     304                average = average / cs.size();
     305
     306                // if one of the nodes is a heading node, forget about the average and use its value
     307                for (Node fn : headingNodes) {
     308                    if (cs.contains(fn)) {
     309                        average = nC.get(fn);
    307310                    }
    308 
    309                 } else {
    310                     align0 = alignb;
    311                     node0 = nodeb;
    312                 }
    313             }
    314             MoveCommand cmd = alignSide(findNodesToAlign(oldWay, nodeb, node0), alignb, align0);
    315             if (cmd != null) {
    316                 cmds.add(cmd);
    317             }
    318         }
    319 
    320         if (cmds.size() > 0) {
    321             Main.main.undoRedo.add(new SequenceCommand(tr("Orthogonalize"), cmds));
    322             Main.map.repaint();
    323         }
    324     }
    325 
    326     private MoveCommand alignSide(ArrayList<Node> aNodes, EastNorth aligna, EastNorth alignb) {
    327 
    328         // Find out co-ords of A and B
    329         double ax = aligna.east();
    330         double ay = aligna.north();
    331         double bx = alignb.east();
    332         double by = alignb.north();
    333 
    334         // OK, for each node to move, work out where to move it!
    335         for (Node n1 : aNodes) {
    336             // Get existing co-ords of node to move
    337             double nx = n1.getEastNorth().east();
    338             double ny = n1.getEastNorth().north();
    339 
    340             if (ax == bx) {
    341                 // Special case if AB is vertical...
    342                 nx = ax;
    343             } else if (ay == by) {
    344                 // ...or horizontal
    345                 ny = ay;
    346             } else {
    347                 // Otherwise calculate position by solving y=mx+c
    348                 double m1 = (by - ay) / (bx - ax);
    349                 double c1 = ay - (ax * m1);
    350                 double m2 = (-1) / m1;
    351                 double c2 = n1.getEastNorth().north() - (n1.getEastNorth().east() * m2);
    352 
    353                 nx = (c2 - c1) / (m1 - m2);
    354                 ny = (m1 * nx) + c1;
    355             }
    356 
    357             // Return the command to move the node to its new position.
    358             return new MoveCommand(n1, nx - n1.getEastNorth().east(), ny - n1.getEastNorth().north());
    359         }
    360         return null;
    361     }
    362 
    363     private ArrayList<Node> findNodesToAlign(Way w, Node from, Node to) {
    364         ArrayList<Node> l = new ArrayList<Node>();
    365         boolean start = false;
    366         for (int i = 0; i < w.getNodesCount(); i++) {
    367             Node n = w.getNode(i % w.getNodesCount());
    368             if (n.equals(to)) {
    369                 break;
    370             }
    371             if (start) {
    372                 l.add(n);
    373             }
    374             if (n.equals(from)) {
    375                 start = true;
    376             }
    377 
    378         }
    379         return l;
    380     }
    381 
    382     static double det(double a, double b, double c, double d)
    383     {
    384         return a * d - b * c;
    385     }
    386 
    387     static double normalize_angle(double h) {
    388         return normalize_angle(h, 0.0);
    389     }
    390     static double normalize_angle(double h, double align_to) {
    391         double llimit = -Math.PI/4;
    392         double ulimit = Math.PI/4;
    393         while (h - align_to > ulimit) {
    394             h -= Math.PI/2;
    395         }
    396         while (h - align_to < llimit) {
    397             h += Math.PI/2;
    398         }
    399 
    400         return h;
    401     }
    402 
    403     static double heading_diff(double h1, double h2) {
    404         double heading_delta = h1 > h2 ? h1 - h2 : h2 - h1;
    405         return heading_delta;
    406     }
    407 
     311                }
     312
     313                for (Node n : cs) {
     314                    nC.put(n, average);
     315                }
     316
     317                for (Node n : cs) {
     318                    s.remove(n);
     319                }
     320            }
     321            if (!s.isEmpty()) throw new RuntimeException();
     322        }
     323
     324        // rotate back and log the change
     325        final Collection<Command> commands = new LinkedList<Command>();
     326        OrthogonalizeAction.rememberMovements.clear();
     327        for (Node n: allNodes) {
     328            EastNorth tmp = new EastNorth(nX.get(n), nY.get(n));
     329            tmp = EN.rotate_cc(pivot, tmp, headingAll);
     330            final double dx = tmp.east()  - n.getEastNorth().east();
     331            final double dy = tmp.north() - n.getEastNorth().north();
     332            if (headingNodes.contains(n)) { // The heading nodes should not have changed
     333                final double EPSILON = 1E-6;
     334                if (Math.abs(dx) > Math.abs(EPSILON * tmp.east()) ||
     335                    Math.abs(dy) > Math.abs(EPSILON * tmp.east())) {
     336                    throw new AssertionError();
     337                }
     338            }
     339            else {
     340                OrthogonalizeAction.rememberMovements.put(n, new EastNorth(dx, dy));
     341                commands.add(new MoveCommand(n, dx, dy));
     342            }
     343        }
     344        Main.main.undoRedo.add(new SequenceCommand(tr("Orthogonalize"), commands));
     345        Main.map.repaint();
     346    }
     347   
     348
     349    /**
     350     * Class contains everything we need to know about a singe way.
     351     */
     352    private static class WayData {
     353        final public Way way;             // The assigned way
     354        final public int nSeg;            // Number of Segments of the Way
     355        final public int nNode;           // Number of Nodes of the Way
     356        public Direction[] segDirections; // Direction of the segments
     357                                          // segment i goes from node i to node (i+1)
     358        public EastNorth segSum;          // (Vector-)sum of all horizontal segments plus the sum of all vertical
     359                                          //     segments turned by 90 degrees
     360        public double heading;            // heading of segSum == approximate heading of the way
     361        public WayData(Way pWay) {
     362            way = pWay;
     363            nNode = way.getNodes().size();
     364            nSeg = nNode - 1;
     365        }
     366        /**
     367         * Estimate the direction of the segments, given the first segment points in the
     368         * direction <code>pInitialDirection</code>.
     369         * Then sum up all horizontal / vertical segments to have a good guess for the
     370         * heading of the entire way.
     371         */
     372        public void calcDirections(Direction pInitialDirection) throws InvalidUserInputException {
     373            final EastNorth[] en = new EastNorth[nNode]; // alias: way.getNodes().get(i).getEastNorth() ---> en[i]
     374            for (int i=0; i < nNode; i++) {
     375                en[i] = new EastNorth(way.getNodes().get(i).getEastNorth().east(), way.getNodes().get(i).getEastNorth().north());
     376            }
     377            segDirections = new Direction[nSeg];
     378            Direction direction = pInitialDirection;
     379            segDirections[0] = direction;
     380            for (int i=0; i < nSeg - 1; i++) {
     381                double h1 = EN.polar(en[i],en[i+1]);
     382                double h2 = EN.polar(en[i+1],en[i+2]);
     383                try {
     384                    direction = direction.changeBy(angleToDirectionChange(h2 - h1, TOLERANCE1));
     385                } catch (RejectedAngleException ex) {
     386                    throw new InvalidUserInputException("Please select ways with angles of approximately 90 or 180 degrees.");
     387                }
     388                segDirections[i+1] = direction;
     389            }
     390
     391            // sum up segments
     392            EastNorth h = new EastNorth(0.,0.);
     393            double lh = EN.abs(h);
     394            EastNorth v = new EastNorth(0.,0.);
     395            double lv = EN.abs(v);
     396            for (int i = 0; i < nSeg; ++i) {
     397                EastNorth segment = EN.diff(en[i+1], en[i]);
     398                if      (segDirections[i] == Direction.RIGHT) h = EN.sum(h,segment);
     399                else if (segDirections[i] == Direction.UP)    v = EN.sum(v,segment);
     400                else if (segDirections[i] == Direction.LEFT)  h = EN.diff(h,segment);
     401                else if (segDirections[i] == Direction.DOWN)  v = EN.diff(v,segment);
     402                else throw new IllegalStateException();
     403                /**
     404                 * When summing up the length of the sum vector should increase.
     405                 * However, it is possible to construct ways, such that this assertion fails.
     406                 * So only uncomment this for testing
     407                 **/
     408//                if (segDirections[i].ordinal() % 2 == 0) {
     409//                    if (EN.abs(h) < lh) throw new AssertionError();
     410//                    lh = EN.abs(h);
     411//                } else {
     412//                    if (EN.abs(v) < lv) throw new AssertionError();
     413//                    lv = EN.abs(v);
     414//                }
     415            }
     416            // rotate the vertical vector by 90 degrees (clockwise) and add it to the horizontal vector
     417            segSum = EN.sum(h, new EastNorth(v.north(), - v.east()));
     418//            if (EN.abs(segSum) < lh) throw new AssertionError();
     419            this.heading = EN.polar(new EastNorth(0.,0.), segSum);
     420        }
     421    }
     422
     423    private enum Direction {
     424        RIGHT, UP, LEFT, DOWN;
     425        public Direction changeBy(int directionChange) {
     426            int tmp = (this.ordinal() + directionChange) % 4;
     427            if (tmp < 0) tmp += 4;          // the % operator can return negative value
     428            return Direction.values()[tmp];
     429        }
     430    }
     431
     432    /**
     433     * Make sure angle (up to 2*Pi) is in interval [ 0, 2*Pi ).
     434     */
     435    private static double standard_angle_0_to_2PI(double a) {
     436        while (a >= 2 * Math.PI) a -= 2 * Math.PI;
     437        while (a < 0)            a += 2 * Math.PI;
     438        return a;
     439    }
     440
     441    /**
     442     * Make sure angle (up to 2*Pi) is in interval ( -Pi, Pi ].
     443     */
     444    private static double standard_angle_mPI_to_PI(double a) {
     445        while (a > Math.PI)    a -= 2 * Math.PI;
     446        while (a <= - Math.PI) a += 2 * Math.PI;
     447        return a;
     448    }
     449
     450    /**
     451     * Class contains some auxiliary functions
     452     */
     453    private static class EN {
     454        // rotate counter-clock-wise
     455        public static EastNorth rotate_cc(EastNorth pivot, EastNorth en, double angle) {
     456            double cosPhi = Math.cos(angle);
     457            double sinPhi = Math.sin(angle);
     458            double x = en.east() - pivot.east();
     459            double y = en.north() - pivot.north();
     460            double nx =  cosPhi * x - sinPhi * y + pivot.east();
     461            double ny =  sinPhi * x + cosPhi * y + pivot.north();
     462            return new EastNorth(nx, ny);
     463        }
     464        public static EastNorth sum(EastNorth en1, EastNorth en2) {
     465            return new EastNorth(en1.east() + en2.east(), en1.north() + en2.north());
     466        }
     467        public static EastNorth diff(EastNorth en1, EastNorth en2) {
     468            return new EastNorth(en1.east() - en2.east(), en1.north() - en2.north());
     469        }
     470        public static double abs(EastNorth en) {
     471            return Math.sqrt(en.east() * en.east() + en.north() * en.north());
     472        }
     473        public static String toString(EastNorth en) {
     474            return "["+u(en.east())+","+u(en.north())+"]";
     475        }
     476        public static long u(double d) {
     477            return Math.round(d * 1000000.);
     478        }
     479        public static double polar(EastNorth en1, EastNorth en2) {
     480            return Math.atan2(en2.north() - en1.north(), en2.east() -  en1.east());
     481        }
     482    }
     483
     484    /**
     485     * Recognize angle to be approximately 0, 90, 180 or 270 degrees.
     486     * returns a integral value, corresponding to a counter clockwise turn:
     487     */
     488    private static int angleToDirectionChange(double a, double deltaMax) throws RejectedAngleException {
     489        a = standard_angle_mPI_to_PI(a);
     490        double d0    = Math.abs(a);
     491        double d90   = Math.abs(a - Math.PI / 2);
     492        double d_m90 = Math.abs(a + Math.PI / 2);
     493        int dirChange;
     494        if (d0 < deltaMax)         dirChange =  0;
     495        else if (d90 < deltaMax)   dirChange =  1;
     496        else if (d_m90 < deltaMax) dirChange = -1;
     497        else {
     498            a = standard_angle_0_to_2PI(a);
     499            double d180 = Math.abs(a - Math.PI);
     500            if (d180 < deltaMax)   dirChange = 2;
     501            else {
     502                throw new RejectedAngleException();
     503            }
     504        }
     505        return dirChange;
     506    }
     507
     508    /**
     509     * Exception: unsuited user input
     510     */
     511    private static class InvalidUserInputException extends Exception {       
     512        InvalidUserInputException(String message) {
     513            super(message);
     514        }
     515        InvalidUserInputException() {
     516            super();
     517        }
     518    }
     519    /**
     520     * Exception: angle cannot be recognized as 0, 90, 180 or 270 degrees
     521     */
     522    private static class RejectedAngleException extends Exception {
     523        RejectedAngleException() {
     524            super();
     525        }
     526    }
     527
     528    /**
     529     * Don't check, if the current selection is suited for orthogonalization.
     530     * Instead, show a usage dialog, that explains, why it cannot be done.
     531     */
    408532    @Override
    409533    protected void updateEnabledState() {
    410         if (getCurrentDataSet() == null) {
    411             setEnabled(false);
    412         } else {
    413             updateEnabledState(getCurrentDataSet().getSelected());
    414         }
    415     }
    416 
    417     @Override
    418     protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
    419         setEnabled(selection != null && !selection.isEmpty());
     534        setEnabled(getCurrentDataSet() != null);
    420535    }
    421536}
  • trunk/src/org/openstreetmap/josm/gui/MainMenu.java

    r2253 r2268  
    134134    public final JosmAction alignInLine = new AlignInLineAction();
    135135    public final JosmAction distribute = new DistributeAction();
    136     public final JosmAction ortho = new OrthogonalizeAction();
     136    public final OrthogonalizeAction ortho = new OrthogonalizeAction();
     137    public final JosmAction orthoUndo = ortho.new Undo();  // action is not shown in the menu. Only triggered by shortcut
    137138    public final JosmAction mirror = new MirrorAction();
    138139    public final AddNodeAction addnode = new AddNodeAction();
Note: See TracChangeset for help on using the changeset viewer.