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.Collection;
010import java.util.HashSet;
011import java.util.Iterator;
012import java.util.LinkedList;
013import java.util.List;
014import java.util.Set;
015
016import javax.swing.JOptionPane;
017
018import org.openstreetmap.josm.command.Command;
019import org.openstreetmap.josm.command.MoveCommand;
020import org.openstreetmap.josm.command.SequenceCommand;
021import org.openstreetmap.josm.data.UndoRedoHandler;
022import org.openstreetmap.josm.data.osm.Node;
023import org.openstreetmap.josm.data.osm.OsmPrimitive;
024import org.openstreetmap.josm.data.osm.Way;
025import org.openstreetmap.josm.gui.Notification;
026import org.openstreetmap.josm.tools.Logging;
027import org.openstreetmap.josm.tools.Shortcut;
028
029/**
030 * Distributes the selected nodes to equal distances along a line.
031 *
032 * @author Teemu Koskinen
033 */
034public final class DistributeAction extends JosmAction {
035
036    /**
037     * Constructs a new {@code DistributeAction}.
038     */
039    public DistributeAction() {
040        super(tr("Distribute Nodes"), "distribute",
041              tr("Distribute the selected nodes to equal distances along a line."),
042              Shortcut.registerShortcut("tools:distribute", tr("Tools: {0}", tr("Distribute Nodes")), KeyEvent.VK_B, Shortcut.SHIFT),
043              true);
044        setHelpId(ht("/Action/DistributeNodes"));
045    }
046
047    /**
048     * Perform action.
049     * Select method according to user selection.
050     * Case 1: One Way (no self-crossing) and at most 2 nodes contains by this way:
051     *     Distribute nodes keeping order along the way
052     * Case 2: Other
053     *     Distribute nodes
054     */
055    @Override
056    public void actionPerformed(ActionEvent e) {
057        if (!isEnabled())
058            return;
059
060        // Collect user selected objects
061        Collection<OsmPrimitive> selected = getLayerManager().getEditDataSet().getSelected();
062        Collection<Way> ways = new LinkedList<>();
063        Collection<Node> nodes = new HashSet<>();
064        for (OsmPrimitive osm : selected) {
065            if (osm instanceof Node) {
066                nodes.add((Node) osm);
067            } else if (osm instanceof Way) {
068                ways.add((Way) osm);
069            }
070        }
071
072        Set<Node> ignoredNodes = removeNodesWithoutCoordinates(nodes);
073        if (!ignoredNodes.isEmpty()) {
074            Logging.warn(tr("Ignoring {0} nodes with null coordinates", ignoredNodes.size()));
075            ignoredNodes.clear();
076        }
077
078        // Switch between algorithms
079        Collection<Command> cmds;
080        if (checkDistributeWay(ways, nodes)) {
081            cmds = distributeWay(ways, nodes);
082        } else if (checkDistributeNodes(ways, nodes)) {
083            cmds = distributeNodes(nodes);
084        } else {
085            new Notification(
086                             tr("Please select :\n" +
087                                "* One no self-crossing way with at most two of its nodes;\n" +
088                                "* Three nodes."))
089                .setIcon(JOptionPane.INFORMATION_MESSAGE)
090                .setDuration(Notification.TIME_SHORT)
091                .show();
092            return;
093        }
094
095        if (cmds.isEmpty()) {
096            return;
097        }
098
099        // Do it!
100        UndoRedoHandler.getInstance().add(new SequenceCommand(tr("Distribute Nodes"), cmds));
101    }
102
103    /**
104     * Test if one way, no self-crossing, is selected with at most two of its nodes.
105     * @param ways Selected ways
106     * @param nodes Selected nodes
107     * @return true in this case
108     */
109    private static boolean checkDistributeWay(Collection<Way> ways, Collection<Node> nodes) {
110        if (ways.size() == 1 && nodes.size() <= 2) {
111            Way w = ways.iterator().next();
112            Set<Node> unduplicated = new HashSet<>(w.getNodes());
113            if (unduplicated.size() != w.getNodesCount()) {
114                // No self crossing way
115                return false;
116            }
117            return nodes.stream().allMatch(w::containsNode);
118        }
119        return false;
120    }
121
122    /**
123     * Distribute nodes contained by a way, keeping nodes order.
124     * If one or two nodes are selected, keep these nodes in place.
125     * @param ways Selected ways, must be collection of size 1.
126     * @param nodes Selected nodes, at most two nodes.
127     * @return Collection of command to be executed.
128     */
129    private static Collection<Command> distributeWay(Collection<Way> ways,
130                                              Collection<Node> nodes) {
131        Way w = ways.iterator().next();
132        Collection<Command> cmds = new LinkedList<>();
133
134        if (w.getNodesCount() == nodes.size() || w.getNodesCount() <= 2) {
135            // Nothing to do
136            return cmds;
137        }
138
139        double xa, ya; // Start point
140        double dx, dy; // Segment increment
141        if (nodes.isEmpty()) {
142            Node na = w.firstNode();
143            nodes.add(na);
144            Node nb = w.lastNode();
145            nodes.add(nb);
146            xa = na.getEastNorth().east();
147            ya = na.getEastNorth().north();
148            dx = (nb.getEastNorth().east() - xa) / (w.getNodesCount() - 1);
149            dy = (nb.getEastNorth().north() - ya) / (w.getNodesCount() - 1);
150        } else if (nodes.size() == 1) {
151            Node n = nodes.iterator().next();
152            int nIdx = w.getNodes().indexOf(n);
153            Node na = w.firstNode();
154            Node nb = w.lastNode();
155            dx = (nb.getEastNorth().east() - na.getEastNorth().east()) /
156                (w.getNodesCount() - 1);
157            dy = (nb.getEastNorth().north() - na.getEastNorth().north()) /
158                (w.getNodesCount() - 1);
159            xa = n.getEastNorth().east() - dx * nIdx;
160            ya = n.getEastNorth().north() - dy * nIdx;
161        } else {
162            Iterator<Node> it = nodes.iterator();
163            Node na = it.next();
164            Node nb = it.next();
165            List<Node> wayNodes = w.getNodes();
166            int naIdx = wayNodes.indexOf(na);
167            int nbIdx = wayNodes.indexOf(nb);
168            dx = (nb.getEastNorth().east() - na.getEastNorth().east()) / (nbIdx - naIdx);
169            dy = (nb.getEastNorth().north() - na.getEastNorth().north()) / (nbIdx - naIdx);
170            xa = na.getEastNorth().east() - dx * naIdx;
171            ya = na.getEastNorth().north() - dy * naIdx;
172        }
173
174        for (int i = 0; i < w.getNodesCount(); i++) {
175            Node n = w.getNode(i);
176            if (!n.isLatLonKnown() || nodes.contains(n)) {
177                continue;
178            }
179            double x = xa + i * dx;
180            double y = ya + i * dy;
181            cmds.add(new MoveCommand(n, x - n.getEastNorth().east(),
182                                     y - n.getEastNorth().north()));
183        }
184        return cmds;
185    }
186
187    /**
188     * Test if nodes oriented algorithm applies to the selection.
189     * @param ways Selected ways
190     * @param nodes Selected nodes
191     * @return true in this case
192     */
193    private static boolean checkDistributeNodes(Collection<Way> ways, Collection<Node> nodes) {
194        return ways.isEmpty() && nodes.size() >= 3;
195    }
196
197    /**
198     * Distribute nodes when only nodes are selected.
199     * The general algorithm here is to find the two selected nodes
200     * that are furthest apart, and then to distribute all other selected
201     * nodes along the straight line between these nodes.
202     * @param nodes nodes to distribute
203     * @return Commands to execute to perform action
204     * @throws IllegalArgumentException if nodes is empty
205     */
206    private static Collection<Command> distributeNodes(Collection<Node> nodes) {
207        // Find from the selected nodes two that are the furthest apart.
208        // Let's call them A and B.
209        double distance = Double.NEGATIVE_INFINITY;
210
211        Node nodea = null;
212        Node nodeb = null;
213
214        Collection<Node> itnodes = new LinkedList<>(nodes);
215        for (Node n : nodes) {
216            itnodes.remove(n);
217            for (Node m : itnodes) {
218                double dist = Math.sqrt(n.getEastNorth().distance(m.getEastNorth()));
219                if (dist > distance) {
220                    nodea = n;
221                    nodeb = m;
222                    distance = dist;
223                }
224            }
225        }
226
227        if (nodea == null || nodeb == null) {
228            throw new IllegalArgumentException();
229        }
230
231        // Remove the nodes A and B from the list of nodes to move
232        nodes.remove(nodea);
233        nodes.remove(nodeb);
234
235        // Find out co-ords of A and B
236        double ax = nodea.getEastNorth().east();
237        double ay = nodea.getEastNorth().north();
238        double bx = nodeb.getEastNorth().east();
239        double by = nodeb.getEastNorth().north();
240
241        // A list of commands to do
242        Collection<Command> cmds = new LinkedList<>();
243
244        // Amount of nodes between A and B plus 1
245        int num = nodes.size()+1;
246
247        // Current number of node
248        int pos = 0;
249        while (!nodes.isEmpty()) {
250            pos++;
251            Node s = null;
252
253            // Find the node that is furthest from B (i.e. closest to A)
254            distance = Double.NEGATIVE_INFINITY;
255            for (Node n : nodes) {
256                double dist = Math.sqrt(nodeb.getEastNorth().distance(n.getEastNorth()));
257                if (dist > distance) {
258                    s = n;
259                    distance = dist;
260                }
261            }
262
263            if (s != null) {
264                // First move the node to A's position, then move it towards B
265                double dx = ax - s.getEastNorth().east() + (bx-ax)*pos/num;
266                double dy = ay - s.getEastNorth().north() + (by-ay)*pos/num;
267
268                cmds.add(new MoveCommand(s, dx, dy));
269
270                //remove moved node from the list
271                nodes.remove(s);
272            }
273        }
274
275        return cmds;
276    }
277
278    /**
279     * Remove nodes without known coordinates from a collection.
280     * @param col Collection of nodes to check
281     * @return Set of nodes without coordinates
282     */
283    private static Set<Node> removeNodesWithoutCoordinates(Collection<Node> col) {
284        Set<Node> result = new HashSet<>();
285        for (Iterator<Node> it = col.iterator(); it.hasNext();) {
286            Node n = it.next();
287            if (!n.isLatLonKnown()) {
288                it.remove();
289                result.add(n);
290            }
291        }
292        return result;
293    }
294
295    @Override
296    protected void updateEnabledState() {
297        updateEnabledStateOnCurrentSelection();
298    }
299
300    @Override
301    protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
302        updateEnabledStateOnModifiableSelection(selection);
303    }
304}