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