001    // License: GPL. See LICENSE file for details.
002    //
003    package org.openstreetmap.josm.actions;
004    
005    import static org.openstreetmap.josm.gui.help.HelpUtil.ht;
006    import static org.openstreetmap.josm.tools.I18n.tr;
007    
008    import java.awt.event.ActionEvent;
009    import java.awt.event.KeyEvent;
010    import java.util.ArrayList;
011    import java.util.Arrays;
012    import java.util.Collection;
013    import java.util.Collections;
014    import java.util.HashMap;
015    import java.util.HashSet;
016    import java.util.Iterator;
017    import java.util.LinkedList;
018    import java.util.List;
019    import java.util.Set;
020    
021    import javax.swing.JOptionPane;
022    
023    import org.openstreetmap.josm.Main;
024    import org.openstreetmap.josm.command.Command;
025    import org.openstreetmap.josm.command.MoveCommand;
026    import org.openstreetmap.josm.command.SequenceCommand;
027    import org.openstreetmap.josm.data.coor.EastNorth;
028    import org.openstreetmap.josm.data.osm.Node;
029    import org.openstreetmap.josm.data.osm.OsmPrimitive;
030    import org.openstreetmap.josm.data.osm.Way;
031    import org.openstreetmap.josm.gui.ConditionalOptionPaneUtil;
032    import org.openstreetmap.josm.tools.Shortcut;
033    
034    /**
035     * Tools / Orthogonalize
036     *
037     * Align edges of a way so all angles are angles of 90 or 180 degrees.
038     * See USAGE String below.
039     */
040    public final class OrthogonalizeAction extends JosmAction {
041        private String USAGE = tr(
042                "<h3>When one or more ways are selected, the shape is adjusted such, that all angles are 90 or 180 degrees.</h3>"+
043                "You can add two nodes to the selection. Then, the direction is fixed by these two reference nodes. "+
044                "(Afterwards, you can undo the movement for certain nodes:<br>"+
045        "Select them and press the shortcut for Orthogonalize / Undo. The default is Shift-Q.)");
046    
047        public OrthogonalizeAction() {
048            super(tr("Orthogonalize Shape"),
049                    "ortho",
050                    tr("Move nodes so all angles are 90 or 180 degrees"),
051                    Shortcut.registerShortcut("tools:orthogonalize", tr("Tool: {0}", tr("Orthogonalize Shape")),
052                            KeyEvent.VK_Q,
053                            Shortcut.DIRECT), true);
054            putValue("help", ht("/Action/OrthogonalizeShape"));
055        }
056    
057        /**
058         * excepted deviation from an angle of 0, 90, 180, 360 degrees
059         * maximum value: 45 degrees
060         *
061         * Current policy is to except just everything, no matter how strange the result would be.
062         */
063        private static final double TOLERANCE1 = Math.toRadians(45.);   // within a way
064        private static final double TOLERANCE2 = Math.toRadians(45.);   // ways relative to each other
065    
066        /**
067         * Remember movements, so the user can later undo it for certain nodes
068         */
069        private static final HashMap<Node, EastNorth> rememberMovements = new HashMap<Node, EastNorth>();
070    
071        /**
072         * Undo the previous orthogonalization for certain nodes.
073         *
074         * This is useful, if the way shares nodes that you don't like to change, e.g. imports or
075         * work of another user.
076         *
077         * This action can be triggered by shortcut only.
078         */
079        public static class Undo extends JosmAction {
080            public Undo() {
081                super(tr("Orthogonalize Shape / Undo"), "ortho",
082                        tr("Undo orthogonalization for certain nodes"),
083                        Shortcut.registerShortcut("tools:orthogonalizeUndo", tr("Tool: {0}", tr("Orthogonalize Shape / Undo")),
084                                KeyEvent.VK_Q,
085                                Shortcut.SHIFT),
086                        true, "action/orthogonalize/undo", true);
087            }
088            public void actionPerformed(ActionEvent e) {
089                if (!isEnabled())
090                    return;
091                final Collection<Command> commands = new LinkedList<Command>();
092                final Collection<OsmPrimitive> sel = getCurrentDataSet().getSelected();
093                try {
094                    for (OsmPrimitive p : sel) {
095                        if (! (p instanceof Node)) throw new InvalidUserInputException();
096                        Node n = (Node) p;
097                        if (rememberMovements.containsKey(n)) {
098                            EastNorth tmp = rememberMovements.get(n);
099                            commands.add(new MoveCommand(n, - tmp.east(), - tmp.north()));
100                            rememberMovements.remove(n);
101                        }
102                    }
103                    if (commands.size() > 0) {
104                        Main.main.undoRedo.add(new SequenceCommand(tr("Orthogonalize / Undo"), commands));
105                        Main.map.repaint();
106                    } else throw new InvalidUserInputException();
107                }
108                catch (InvalidUserInputException ex) {
109                    JOptionPane.showMessageDialog(
110                            Main.parent,
111                            tr("Orthogonalize Shape / Undo\n"+
112                            "Please select nodes that were moved by the previous Orthogonalize Shape action!"),
113                            tr("Undo Orthogonalize Shape"),
114                            JOptionPane.INFORMATION_MESSAGE);
115                }
116            }
117        }
118    
119        public void actionPerformed(ActionEvent e) {
120            if (!isEnabled())
121                return;
122            if ("EPSG:4326".equals(Main.getProjection().toString())) {
123                String msg = tr("<html>You are using the EPSG:4326 projection which might lead<br>" +
124                        "to undesirable results when doing rectangular alignments.<br>" +
125                        "Change your projection to get rid of this warning.<br>" +
126                "Do you want to continue?</html>");
127                if (!ConditionalOptionPaneUtil.showConfirmationDialog(
128                        "align_rectangular_4326",
129                        Main.parent,
130                        msg,
131                        tr("Warning"),
132                        JOptionPane.YES_NO_OPTION,
133                        JOptionPane.QUESTION_MESSAGE,
134                        JOptionPane.YES_OPTION))
135                    return;
136            }
137    
138            final ArrayList<Node> nodeList = new ArrayList<Node>();
139            final ArrayList<WayData> wayDataList = new ArrayList<WayData>();
140            final Collection<OsmPrimitive> sel = getCurrentDataSet().getSelected();
141    
142            try {
143                // collect nodes and ways from the selection
144                for (OsmPrimitive p : sel) {
145                    if (p instanceof Node) {
146                        nodeList.add((Node) p);
147                    }
148                    else if (p instanceof Way) {
149                        wayDataList.add(new WayData((Way) p));
150                    } else
151                        throw new InvalidUserInputException(tr("Selection must consist only of ways and nodes."));
152                }
153                if (wayDataList.isEmpty())
154                    throw new InvalidUserInputException("usage");
155                else  {
156                    if (nodeList.size() == 2 || nodeList.isEmpty()) {
157                        OrthogonalizeAction.rememberMovements.clear();
158                        final Collection<Command> commands = new LinkedList<Command>();
159    
160                        if (nodeList.size() == 2) {  // fixed direction
161                            commands.addAll(orthogonalize(wayDataList, nodeList));
162                        }
163                        else if (nodeList.isEmpty()) {
164                            List<ArrayList<WayData>> groups = buildGroups(wayDataList);
165                            for (ArrayList<WayData> g: groups) {
166                                commands.addAll(orthogonalize(g, nodeList));
167                            }
168                        } else
169                            throw new IllegalStateException();
170    
171                        Main.main.undoRedo.add(new SequenceCommand(tr("Orthogonalize"), commands));
172                        Main.map.repaint();
173    
174                    } else
175                        throw new InvalidUserInputException("usage");
176                }
177            } catch (InvalidUserInputException ex) {
178                if (ex.getMessage().equals("usage")) {
179                    JOptionPane.showMessageDialog(
180                            Main.parent,
181                            "<html><h2>" + tr("Usage") + "</h2>" + USAGE + "</html>",
182                            tr("Orthogonalize Shape"),
183                            JOptionPane.INFORMATION_MESSAGE);
184                }
185                else {
186                    JOptionPane.showMessageDialog(
187                            Main.parent,
188                            "<html>" + ex.getMessage() + "<br><hr><h2>" + tr("Usage") + "</h2>" + USAGE + "</html>",
189                            tr("Selected Elements cannot be orthogonalized"),
190                            JOptionPane.INFORMATION_MESSAGE);
191                }
192            }
193        }
194        
195        /**
196         * Collect groups of ways with common nodes in order to orthogonalize each group separately.
197         */
198        private static List<ArrayList<WayData>> buildGroups(ArrayList<WayData> wayDataList) {
199            List<ArrayList<WayData>> groups = new ArrayList<ArrayList<WayData>>();
200            Set<WayData> remaining = new HashSet<WayData>(wayDataList);
201            while (!remaining.isEmpty()) {
202                ArrayList<WayData> group = new ArrayList<WayData>();
203                groups.add(group);
204                Iterator<WayData> it = remaining.iterator();
205                WayData next = it.next();
206                it.remove();
207                extendGroupRec(group, next, new ArrayList<WayData>(remaining));
208                remaining.removeAll(group);
209            }
210            return groups;
211        }
212        
213        private static void extendGroupRec(List<WayData> group, WayData newGroupMember, List<WayData> remaining) {
214            group.add(newGroupMember);
215            for (int i = 0; i < remaining.size(); ++i) {
216                WayData candidate = remaining.get(i);
217                if (candidate == null) continue;
218                if (!Collections.disjoint(candidate.way.getNodes(), newGroupMember.way.getNodes())) {
219                    remaining.set(i, null);
220                    extendGroupRec(group, candidate, remaining);
221                }
222            }
223        }
224    
225        /**
226         *
227         *  Outline:
228         *  1. Find direction of all segments
229         *      - direction = 0..3 (right,up,left,down)
230         *      - right is not really right, you may have to turn your screen
231         *  2. Find average heading of all segments
232         *      - heading = angle of a vector in polar coordinates
233         *      - sum up horizontal segments (those with direction 0 or 2)
234         *      - sum up vertical segments
235         *      - turn the vertical sum by 90 degrees and add it to the horizontal sum
236         *      - get the average heading from this total sum
237         *  3. Rotate all nodes by the average heading so that right is really right
238         *      and all segments are approximately NS or EW.
239         *  4. If nodes are connected by a horizontal segment: Replace their y-Coordinate by
240         *      the mean value of their y-Coordinates.
241         *      - The same for vertical segments.
242         *  5. Rotate back.
243         *
244         **/
245        private static Collection<Command> orthogonalize(ArrayList<WayData> wayDataList, ArrayList<Node> headingNodes)
246        throws InvalidUserInputException
247        {
248            // find average heading
249            double headingAll;
250            try {
251                if (headingNodes.isEmpty()) {
252                    // find directions of the segments and make them consistent between different ways
253                    wayDataList.get(0).calcDirections(Direction.RIGHT);
254                    double refHeading = wayDataList.get(0).heading;
255                    for (WayData w : wayDataList) {
256                        w.calcDirections(Direction.RIGHT);
257                        int directionOffset = angleToDirectionChange(w.heading - refHeading, TOLERANCE2);
258                        w.calcDirections(Direction.RIGHT.changeBy(directionOffset));
259                        if (angleToDirectionChange(refHeading - w.heading, TOLERANCE2) != 0) throw new RuntimeException();
260                    }
261                    EastNorth totSum = new EastNorth(0., 0.);
262                    for (WayData w : wayDataList) {
263                        totSum = EN.sum(totSum, w.segSum);
264                    }
265                    headingAll = EN.polar(new EastNorth(0., 0.), totSum);
266                }
267                else {
268                    headingAll = EN.polar(headingNodes.get(0).getEastNorth(), headingNodes.get(1).getEastNorth());
269                    for (WayData w : wayDataList) {
270                        w.calcDirections(Direction.RIGHT);
271                        int directionOffset = angleToDirectionChange(w.heading - headingAll, TOLERANCE2);
272                        w.calcDirections(Direction.RIGHT.changeBy(directionOffset));
273                    }
274                }
275            } catch (RejectedAngleException ex) {
276                throw new InvalidUserInputException(
277                        tr("<html>Please make sure all selected ways head in a similar direction<br>"+
278                        "or orthogonalize them one by one.</html>"));
279            }
280    
281            // put the nodes of all ways in a set
282            final HashSet<Node> allNodes = new HashSet<Node>();
283            for (WayData w : wayDataList) {
284                for (Node n : w.way.getNodes()) {
285                    allNodes.add(n);
286                }
287            }
288    
289            // the new x and y value for each node
290            final HashMap<Node, Double> nX = new HashMap<Node, Double>();
291            final HashMap<Node, Double> nY = new HashMap<Node, Double>();
292    
293            // calculate the centroid of all nodes
294            // it is used as rotation center
295            EastNorth pivot = new EastNorth(0., 0.);
296            for (Node n : allNodes) {
297                pivot = EN.sum(pivot, n.getEastNorth());
298            }
299            pivot = new EastNorth(pivot.east() / allNodes.size(), pivot.north() / allNodes.size());
300    
301            // rotate
302            for (Node n: allNodes) {
303                EastNorth tmp = EN.rotate_cc(pivot, n.getEastNorth(), - headingAll);
304                nX.put(n, tmp.east());
305                nY.put(n, tmp.north());
306            }
307    
308            // orthogonalize
309            final Direction[] HORIZONTAL = {Direction.RIGHT, Direction.LEFT};
310            final Direction[] VERTICAL = {Direction.UP, Direction.DOWN};
311            final Direction[][] ORIENTATIONS = {HORIZONTAL, VERTICAL};
312            for (Direction[] orientation : ORIENTATIONS){
313                final HashSet<Node> s = new HashSet<Node>(allNodes);
314                int s_size = s.size();
315                for (int dummy = 0; dummy < s_size; ++dummy) {
316                    if (s.isEmpty()) {
317                        break;
318                    }
319                    final Node dummy_n = s.iterator().next();     // pick arbitrary element of s
320    
321                    final HashSet<Node> cs = new HashSet<Node>(); // will contain each node that can be reached from dummy_n
322                    cs.add(dummy_n);                              // walking only on horizontal / vertical segments
323    
324                    boolean somethingHappened = true;
325                    while (somethingHappened) {
326                        somethingHappened = false;
327                        for (WayData w : wayDataList) {
328                            for (int i=0; i < w.nSeg; ++i) {
329                                Node n1 = w.way.getNodes().get(i);
330                                Node n2 = w.way.getNodes().get(i+1);
331                                if (Arrays.asList(orientation).contains(w.segDirections[i])) {
332                                    if (cs.contains(n1) && ! cs.contains(n2)) {
333                                        cs.add(n2);
334                                        somethingHappened = true;
335                                    }
336                                    if (cs.contains(n2) && ! cs.contains(n1)) {
337                                        cs.add(n1);
338                                        somethingHappened = true;
339                                    }
340                                }
341                            }
342                        }
343                    }
344    
345                    final HashMap<Node, Double> nC = (orientation == HORIZONTAL) ? nY : nX;
346    
347                    double average = 0;
348                    for (Node n : cs) {
349                        average += nC.get(n).doubleValue();
350                    }
351                    average = average / cs.size();
352    
353                    // if one of the nodes is a heading node, forget about the average and use its value
354                    for (Node fn : headingNodes) {
355                        if (cs.contains(fn)) {
356                            average = nC.get(fn);
357                        }
358                    }
359    
360                    for (Node n : cs) {
361                        nC.put(n, average);
362                    }
363    
364                    for (Node n : cs) {
365                        s.remove(n);
366                    }
367                }
368                if (!s.isEmpty()) throw new RuntimeException();
369            }
370    
371            // rotate back and log the change
372            final Collection<Command> commands = new LinkedList<Command>();
373            //        OrthogonalizeAction.rememberMovements.clear();
374            for (Node n: allNodes) {
375                EastNorth tmp = new EastNorth(nX.get(n), nY.get(n));
376                tmp = EN.rotate_cc(pivot, tmp, headingAll);
377                final double dx = tmp.east()  - n.getEastNorth().east();
378                final double dy = tmp.north() - n.getEastNorth().north();
379                if (headingNodes.contains(n)) { // The heading nodes should not have changed
380                    final double EPSILON = 1E-6;
381                    if (Math.abs(dx) > Math.abs(EPSILON * tmp.east()) ||
382                            Math.abs(dy) > Math.abs(EPSILON * tmp.east()))
383                        throw new AssertionError();
384                }
385                else {
386                    OrthogonalizeAction.rememberMovements.put(n, new EastNorth(dx, dy));
387                    commands.add(new MoveCommand(n, dx, dy));
388                }
389            }
390            return commands;
391        }
392    
393        /**
394         * Class contains everything we need to know about a singe way.
395         */
396        private static class WayData {
397            final public Way way;             // The assigned way
398            final public int nSeg;            // Number of Segments of the Way
399            final public int nNode;           // Number of Nodes of the Way
400            public Direction[] segDirections; // Direction of the segments
401            // segment i goes from node i to node (i+1)
402            public EastNorth segSum;          // (Vector-)sum of all horizontal segments plus the sum of all vertical
403            //     segments turned by 90 degrees
404            public double heading;            // heading of segSum == approximate heading of the way
405            public WayData(Way pWay) {
406                way = pWay;
407                nNode = way.getNodes().size();
408                nSeg = nNode - 1;
409            }
410            /**
411             * Estimate the direction of the segments, given the first segment points in the
412             * direction <code>pInitialDirection</code>.
413             * Then sum up all horizontal / vertical segments to have a good guess for the
414             * heading of the entire way.
415             */
416            public void calcDirections(Direction pInitialDirection) throws InvalidUserInputException {
417                final EastNorth[] en = new EastNorth[nNode]; // alias: way.getNodes().get(i).getEastNorth() ---> en[i]
418                for (int i=0; i < nNode; i++) {
419                    en[i] = new EastNorth(way.getNodes().get(i).getEastNorth().east(), way.getNodes().get(i).getEastNorth().north());
420                }
421                segDirections = new Direction[nSeg];
422                Direction direction = pInitialDirection;
423                segDirections[0] = direction;
424                for (int i=0; i < nSeg - 1; i++) {
425                    double h1 = EN.polar(en[i],en[i+1]);
426                    double h2 = EN.polar(en[i+1],en[i+2]);
427                    try {
428                        direction = direction.changeBy(angleToDirectionChange(h2 - h1, TOLERANCE1));
429                    } catch (RejectedAngleException ex) {
430                        throw new InvalidUserInputException(tr("Please select ways with angles of approximately 90 or 180 degrees."));
431                    }
432                    segDirections[i+1] = direction;
433                }
434    
435                // sum up segments
436                EastNorth h = new EastNorth(0.,0.);
437                //double lh = EN.abs(h);
438                EastNorth v = new EastNorth(0.,0.);
439                //double lv = EN.abs(v);
440                for (int i = 0; i < nSeg; ++i) {
441                    EastNorth segment = EN.diff(en[i+1], en[i]);
442                    if      (segDirections[i] == Direction.RIGHT) {
443                        h = EN.sum(h,segment);
444                    } else if (segDirections[i] == Direction.UP) {
445                        v = EN.sum(v,segment);
446                    } else if (segDirections[i] == Direction.LEFT) {
447                        h = EN.diff(h,segment);
448                    } else if (segDirections[i] == Direction.DOWN) {
449                        v = EN.diff(v,segment);
450                    } else throw new IllegalStateException();
451                    /**
452                     * When summing up the length of the sum vector should increase.
453                     * However, it is possible to construct ways, such that this assertion fails.
454                     * So only uncomment this for testing
455                     **/
456                    //                if (segDirections[i].ordinal() % 2 == 0) {
457                    //                    if (EN.abs(h) < lh) throw new AssertionError();
458                    //                    lh = EN.abs(h);
459                    //                } else {
460                    //                    if (EN.abs(v) < lv) throw new AssertionError();
461                    //                    lv = EN.abs(v);
462                    //                }
463                }
464                // rotate the vertical vector by 90 degrees (clockwise) and add it to the horizontal vector
465                segSum = EN.sum(h, new EastNorth(v.north(), - v.east()));
466                //            if (EN.abs(segSum) < lh) throw new AssertionError();
467                this.heading = EN.polar(new EastNorth(0.,0.), segSum);
468            }
469        }
470    
471        private enum Direction {
472            RIGHT, UP, LEFT, DOWN;
473            public Direction changeBy(int directionChange) {
474                int tmp = (this.ordinal() + directionChange) % 4;
475                if (tmp < 0) {
476                    tmp += 4;          // the % operator can return negative value
477                }
478                return Direction.values()[tmp];
479            }
480        }
481    
482        /**
483         * Make sure angle (up to 2*Pi) is in interval [ 0, 2*Pi ).
484         */
485        private static double standard_angle_0_to_2PI(double a) {
486            while (a >= 2 * Math.PI) {
487                a -= 2 * Math.PI;
488            }
489            while (a < 0) {
490                a += 2 * Math.PI;
491            }
492            return a;
493        }
494    
495        /**
496         * Make sure angle (up to 2*Pi) is in interval ( -Pi, Pi ].
497         */
498        private static double standard_angle_mPI_to_PI(double a) {
499            while (a > Math.PI) {
500                a -= 2 * Math.PI;
501            }
502            while (a <= - Math.PI) {
503                a += 2 * Math.PI;
504            }
505            return a;
506        }
507    
508        /**
509         * Class contains some auxiliary functions
510         */
511        private static class EN {
512            // rotate counter-clock-wise
513            public static EastNorth rotate_cc(EastNorth pivot, EastNorth en, double angle) {
514                double cosPhi = Math.cos(angle);
515                double sinPhi = Math.sin(angle);
516                double x = en.east() - pivot.east();
517                double y = en.north() - pivot.north();
518                double nx =  cosPhi * x - sinPhi * y + pivot.east();
519                double ny =  sinPhi * x + cosPhi * y + pivot.north();
520                return new EastNorth(nx, ny);
521            }
522            public static EastNorth sum(EastNorth en1, EastNorth en2) {
523                return new EastNorth(en1.east() + en2.east(), en1.north() + en2.north());
524            }
525            public static EastNorth diff(EastNorth en1, EastNorth en2) {
526                return new EastNorth(en1.east() - en2.east(), en1.north() - en2.north());
527            }
528            public static double polar(EastNorth en1, EastNorth en2) {
529                return Math.atan2(en2.north() - en1.north(), en2.east() -  en1.east());
530            }
531        }
532    
533        /**
534         * Recognize angle to be approximately 0, 90, 180 or 270 degrees.
535         * returns an integral value, corresponding to a counter clockwise turn:
536         */
537        private static int angleToDirectionChange(double a, double deltaMax) throws RejectedAngleException {
538            a = standard_angle_mPI_to_PI(a);
539            double d0    = Math.abs(a);
540            double d90   = Math.abs(a - Math.PI / 2);
541            double d_m90 = Math.abs(a + Math.PI / 2);
542            int dirChange;
543            if (d0 < deltaMax) {
544                dirChange =  0;
545            } else if (d90 < deltaMax) {
546                dirChange =  1;
547            } else if (d_m90 < deltaMax) {
548                dirChange = -1;
549            } else {
550                a = standard_angle_0_to_2PI(a);
551                double d180 = Math.abs(a - Math.PI);
552                if (d180 < deltaMax) {
553                    dirChange = 2;
554                } else
555                    throw new RejectedAngleException();
556            }
557            return dirChange;
558        }
559    
560        /**
561         * Exception: unsuited user input
562         */
563        private static class InvalidUserInputException extends Exception {
564            InvalidUserInputException(String message) {
565                super(message);
566            }
567            InvalidUserInputException() {
568                super();
569            }
570        }
571        /**
572         * Exception: angle cannot be recognized as 0, 90, 180 or 270 degrees
573         */
574        private static class RejectedAngleException extends Exception {
575            RejectedAngleException() {
576                super();
577            }
578        }
579    
580        /**
581         * Don't check, if the current selection is suited for orthogonalization.
582         * Instead, show a usage dialog, that explains, why it cannot be done.
583         */
584        @Override
585        protected void updateEnabledState() {
586            setEnabled(getCurrentDataSet() != null);
587        }
588    }