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