source: subversion/applications/editors/josm/plugins/simplifyarea/src/org/openstreetmap/josm/plugins/simplifyarea/SimplifyAreaAction.java

Last change on this file was 34972, checked in by donvip, 10 days ago

see #josm17580 #josm17581 #josm17582 #josm17583 #josm17584 #josm17585 #josm17586 #josm17587 #josm17588 - remove deprecated api (patches by taylor.smock)

File size: 18.4 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.plugins.simplifyarea;
3
4import static java.lang.Math.cos;
5import static java.lang.Math.sin;
6import static java.lang.Math.toRadians;
7import static org.openstreetmap.josm.tools.I18n.tr;
8import static org.openstreetmap.josm.tools.I18n.trn;
9
10import java.awt.event.ActionEvent;
11import java.awt.event.KeyEvent;
12import java.util.ArrayList;
13import java.util.Collection;
14import java.util.HashMap;
15import java.util.HashSet;
16import java.util.List;
17import java.util.Map;
18import java.util.Map.Entry;
19import java.util.Set;
20
21import javax.swing.JOptionPane;
22
23import org.openstreetmap.josm.actions.JosmAction;
24import org.openstreetmap.josm.command.ChangeCommand;
25import org.openstreetmap.josm.command.Command;
26import org.openstreetmap.josm.command.DeleteCommand;
27import org.openstreetmap.josm.command.MoveCommand;
28import org.openstreetmap.josm.command.SequenceCommand;
29import org.openstreetmap.josm.data.Bounds;
30import org.openstreetmap.josm.data.UndoRedoHandler;
31import org.openstreetmap.josm.data.coor.LatLon;
32import org.openstreetmap.josm.data.osm.Node;
33import org.openstreetmap.josm.data.osm.OsmPrimitive;
34import org.openstreetmap.josm.data.osm.OsmPrimitiveType;
35import org.openstreetmap.josm.data.osm.Way;
36import org.openstreetmap.josm.gui.HelpAwareOptionPane;
37import org.openstreetmap.josm.gui.HelpAwareOptionPane.ButtonSpec;
38import org.openstreetmap.josm.gui.MainApplication;
39import org.openstreetmap.josm.spi.preferences.Config;
40import org.openstreetmap.josm.tools.ImageProvider;
41import org.openstreetmap.josm.tools.Shortcut;
42import org.openstreetmap.josm.tools.Utils;
43
44public final class SimplifyAreaAction extends JosmAction {
45
46    public SimplifyAreaAction() {
47        super(tr("Simplify Area"), "simplify", tr("Delete unnecessary nodes from an area."),
48                Shortcut.registerShortcut("tools:simplifyArea", tr("Tool: {0}", tr("Simplify Area")), KeyEvent.VK_Y, Shortcut.CTRL_SHIFT),
49                true, "simplifyarea", true);
50    }
51
52    private List<Bounds> getCurrentEditBounds() {
53        return MainApplication.getLayerManager().getEditLayer().data.getDataSourceBounds();
54    }
55
56    private static boolean isInBounds(final Node node, final List<Bounds> bounds) {
57        for (final Bounds b : bounds) {
58            if (b.contains(node.getCoor())) {
59                return true;
60            }
61        }
62        return false;
63    }
64
65    private static boolean confirmWayWithNodesOutsideBoundingBox() {
66        final ButtonSpec[] options = new ButtonSpec[] { new ButtonSpec(tr("Yes, delete nodes"), ImageProvider.get("ok"), tr("Delete nodes outside of downloaded data regions"), null),
67                new ButtonSpec(tr("No, abort"), ImageProvider.get("cancel"), tr("Cancel operation"), null) };
68        return 0 == HelpAwareOptionPane.showOptionDialog(
69                MainApplication.getMainFrame(),
70                "<html>" + trn("The selected way has nodes outside of the downloaded data region.", "The selected ways have nodes outside of the downloaded data region.", 
71                        MainApplication.getLayerManager().getEditDataSet().getSelectedWays().size())
72                + "<br>" + tr("This can lead to nodes being deleted accidentally.") + "<br>" + tr("Do you want to delete them anyway?") + "</html>",
73                tr("Delete nodes outside of data regions?"), JOptionPane.WARNING_MESSAGE, null, // no special icon
74                options, options[0], null);
75    }
76
77    private void alertSelectAtLeastOneWay() {
78        HelpAwareOptionPane.showOptionDialog(MainApplication.getMainFrame(), tr("Please select at least one way to simplify."), tr("Warning"), JOptionPane.WARNING_MESSAGE, null);
79    }
80
81    private boolean confirmSimplifyManyWays(final int numWays) {
82        final ButtonSpec[] options = new ButtonSpec[] { new ButtonSpec(tr("Yes"), ImageProvider.get("ok"), tr("Simplify all selected ways"), null),
83                new ButtonSpec(tr("Cancel"), ImageProvider.get("cancel"), tr("Cancel operation"), null) };
84        return 0 == HelpAwareOptionPane.showOptionDialog(MainApplication.getMainFrame(), tr("The selection contains {0} ways. Are you sure you want to simplify them all?", numWays), 
85                tr("Simplify ways?"),
86                JOptionPane.WARNING_MESSAGE, null, // no special icon
87                options, options[0], null);
88    }
89
90    @Override
91    public void actionPerformed(final ActionEvent e) {
92        final Collection<OsmPrimitive> selection = getLayerManager().getEditDataSet().getSelected();
93
94        final List<Bounds> bounds = getCurrentEditBounds();
95        for (final OsmPrimitive prim : selection) {
96            if (prim instanceof Way && bounds.size() > 0) {
97                final Way way = (Way) prim;
98                // We check if each node of each way is at least in one download
99                // bounding box. Otherwise nodes may get deleted that are necessary by
100                // unloaded ways (see Ticket #1594)
101                for (final Node node : way.getNodes()) {
102                    if (!isInBounds(node, bounds)) {
103                        if (!confirmWayWithNodesOutsideBoundingBox()) {
104                            return;
105                        }
106                        break;
107                    }
108                }
109            }
110        }
111        final Collection<Way> ways = Utils.filteredCollection(selection, Way.class);
112        if (ways.isEmpty()) {
113            alertSelectAtLeastOneWay();
114            return;
115        } else if (ways.size() > 10) {
116            if (!confirmSimplifyManyWays(ways.size())) {
117                return;
118            }
119        }
120
121        final List<Node> nodesToDelete = new ArrayList<>(); // can contain duplicate instances
122
123        for (final Way way : ways) {
124            addNodesToDelete(nodesToDelete, way);
125        }
126
127        final Map<Node, Integer> nodeCountMap = new HashMap<>();
128        for (final Node node : nodesToDelete) {
129            Integer count = nodeCountMap.get(node);
130            if (count == null) {
131                count = 0;
132            }
133            nodeCountMap.put(node, ++count);
134        }
135
136        final Collection<Node> nodesReallyToRemove = new ArrayList<>();
137
138        for (final Entry<Node, Integer> entry : nodeCountMap.entrySet()) {
139            final Node node = entry.getKey();
140            final Integer count = entry.getValue();
141
142            if (!node.isTagged() && node.getReferrers().size() == count) {
143                nodesReallyToRemove.add(node);
144            }
145        }
146
147        final Collection<Command> allCommands = new ArrayList<>();
148
149        if (!nodesReallyToRemove.isEmpty()) {
150            for (final Way way : ways) {
151                final List<Node> nodes = way.getNodes();
152                final boolean closed = nodes.get(0).equals(nodes.get(nodes.size() - 1));
153                if (closed) {
154                    nodes.remove(nodes.size() - 1);
155                }
156
157                if (nodes.removeAll(nodesReallyToRemove)) {
158                    if (closed) {
159                        nodes.add(nodes.get(0));
160                    }
161
162                    final Way newWay = new Way(way);
163                    newWay.setNodes(nodes);
164                    allCommands.add(new ChangeCommand(way, newWay));
165                }
166            }
167
168            allCommands.add(new DeleteCommand(nodesReallyToRemove));
169        }
170
171        final Collection<Command> avgCommands = averageNearbyNodes(ways, nodesReallyToRemove);
172        if (avgCommands != null && !avgCommands.isEmpty()) {
173            allCommands.add(new SequenceCommand(tr("average nearby nodes"), avgCommands));
174        }
175
176        if (!allCommands.isEmpty()) {
177            final SequenceCommand rootCommand = new SequenceCommand(trn("Simplify {0} way", "Simplify {0} ways", allCommands.size(), allCommands.size()), allCommands);
178            UndoRedoHandler.getInstance().add(rootCommand);
179            MainApplication.getMap().repaint();
180        }
181    }
182
183    private static boolean nodeGluesWays(final Node node) {
184        Set<Node> referenceNeighbours = null;
185        for (final OsmPrimitive ref : node.getReferrers()) {
186            if (ref.getType() == OsmPrimitiveType.WAY) {
187                final Way way = ((Way) ref);
188                final Set<Node> neighbours = way.getNeighbours(node);
189                if (referenceNeighbours == null) {
190                    referenceNeighbours = neighbours;
191                } else if (!referenceNeighbours.containsAll(neighbours)) {
192                    return true;
193                }
194            }
195        }
196       
197        return false;
198    }
199
200    // average nearby nodes
201    private static Collection<Command> averageNearbyNodes(final Collection<Way> ways, final Collection<Node> nodesAlreadyDeleted) {
202        final double mergeThreshold = Config.getPref().getDouble(SimplifyAreaPreferenceSetting.MERGE_THRESHOLD, 0.2);
203
204        final Map<Node, LatLon> coordMap = new HashMap<>();
205        for (final Way way : ways) {
206            for (final Node n : way.getNodes()) {
207                coordMap.put(n, n.getCoor());
208            }
209        }
210
211        coordMap.keySet().removeAll(nodesAlreadyDeleted);
212
213        for (final Way w : ways) {
214            final List<Node> nodes = w.getNodes();
215
216            final Node lastNode = nodes.get(nodes.size() - 1);
217            final boolean closed = nodes.get(0).equals(lastNode);
218            if (closed) {
219                nodes.remove(lastNode);
220            }
221
222            nodes.retainAll(coordMap.keySet()); // removes already deleted nodes
223
224            while (true) {
225                double minDist = Double.POSITIVE_INFINITY;
226                Node node1 = null;
227                Node node2 = null;
228
229                final int len = nodes.size();
230                if (len == 0) {
231                    break;
232                }
233
234                // find smallest distance
235                for (int i = 0; i <= len; i++) {
236                    final Node n1 = nodes.get(i % len);
237                    final Node n2 = nodes.get((i + 1) % len);
238
239                    if (n1.isTagged() || n2.isTagged()) {
240                        continue;
241                    }
242
243                    // test if both nodes are on the same ways
244                    final List<OsmPrimitive> referrers = n1.getReferrers();
245                    if (!ways.containsAll(referrers)) {
246                        continue;
247                    }
248
249                    final List<OsmPrimitive> referrers2 = n2.getReferrers();
250                    if (!ways.containsAll(referrers2)) {
251                        continue;
252                    }
253
254                    // test if both nodes have same parents
255                    if (!referrers.containsAll(referrers2) || !referrers2.containsAll(referrers)) {
256                        continue;
257                    }
258
259                    final LatLon a = coordMap.get(n1);
260                    final LatLon b = coordMap.get(n2);
261                   
262                    if (a != null && b != null) {
263                        final double dist = a.greatCircleDistance(b);
264                        if (dist < minDist && dist < mergeThreshold) {
265                            minDist = dist;
266                            node1 = n1;
267                            node2 = n2;
268                        }
269                    }
270                }
271
272                if (node1 == null || node2 == null) {
273                    break;
274                }
275
276                final LatLon coord = coordMap.get(node1).getCenter(coordMap.get(node2));
277                coordMap.put(node1, coord);
278
279                nodes.remove(node2);
280                coordMap.remove(node2);
281            }
282        }
283
284        final Collection<Command> commands = new ArrayList<>();
285        final Set<Node> nodesToDelete2 = new HashSet<>();
286        for (final Way way : ways) {
287            final List<Node> nodesToDelete = way.getNodes();
288            nodesToDelete.removeAll(nodesAlreadyDeleted);
289            if (nodesToDelete.removeAll(coordMap.keySet())) {
290                nodesToDelete2.addAll(nodesToDelete);
291                final Way newWay = new Way(way);
292                final List<Node> nodes = way.getNodes();
293                final boolean closed = nodes.get(0).equals(nodes.get(nodes.size() - 1));
294                if (closed) {
295                    nodes.remove(nodes.size() - 1);
296                }
297                nodes.retainAll(coordMap.keySet());
298                if (closed) {
299                    nodes.add(nodes.get(0));
300                }
301
302                newWay.setNodes(nodes);
303                if (!way.getNodes().equals(nodes)) {
304                    commands.add(new ChangeCommand(way, newWay));
305                }
306            }
307        }
308
309        if (!nodesToDelete2.isEmpty()) {
310            commands.add(new DeleteCommand(nodesToDelete2));
311        }
312
313        for (final Entry<Node, LatLon> entry : coordMap.entrySet()) {
314            final Node node = entry.getKey();
315            final LatLon coord = entry.getValue();
316            if (!node.getCoor().equals(coord)) {
317                commands.add(new MoveCommand(node, coord));
318            }
319        }
320
321        return commands;
322    }
323
324    private static void addNodesToDelete(final Collection<Node> nodesToDelete, final Way w) {
325        final double angleThreshold = Config.getPref().getDouble(SimplifyAreaPreferenceSetting.ANGLE_THRESHOLD, 10);
326        final double angleFactor = Config.getPref().getDouble(SimplifyAreaPreferenceSetting.ANGLE_FACTOR, 1.0);
327        final double areaThreshold = Config.getPref().getDouble(SimplifyAreaPreferenceSetting.AREA_THRESHOLD, 5.0);
328        final double areaFactor = Config.getPref().getDouble(SimplifyAreaPreferenceSetting.AREA_FACTOR, 1.0);
329        final double distanceThreshold = Config.getPref().getDouble(SimplifyAreaPreferenceSetting.DIST_THRESHOLD, 3);
330        final double distanceFactor = Config.getPref().getDouble(SimplifyAreaPreferenceSetting.DIST_FACTOR, 3);
331
332        final List<Node> nodes = w.getNodes();
333        final int size = nodes.size();
334
335        if (size == 0) {
336            return;
337        }
338
339        final boolean closed = nodes.get(0).equals(nodes.get(size - 1));
340
341        if (closed) {
342            nodes.remove(size - 1); // remove end node ( = start node)
343        }
344
345        // remove nodes within threshold
346
347        final List<Double> weightList = new ArrayList<>(nodes.size()); // weight cache
348        for (int i = 0; i < nodes.size(); i++) {
349            weightList.add(null);
350        }
351
352        while (true) {
353            Node prevNode = null;
354            LatLon coord1 = null;
355            LatLon coord2 = null;
356            int prevIndex = -1;
357
358            double minWeight = Double.POSITIVE_INFINITY;
359            Node bestMatch = null;
360
361            final int size2 = nodes.size();
362
363            if (size2 == 0) {
364                break;
365            }
366
367            for (int i = 0, len = size2 + (closed ? 2 : 1); i < len; i++) {
368                final int index = i % size2;
369
370                final Node n = nodes.get(index);
371                final LatLon coord3 = n.getCoor();
372
373                if (coord1 != null) {
374                    final double weight;
375
376                    if (weightList.get(prevIndex) == null) {
377                        final double angleWeight = computeConvectAngle(coord1, coord2, coord3) / angleThreshold;
378                        final double areaWeight = computeArea(coord1, coord2, coord3) / areaThreshold;
379                        final double distanceWeight = Math.abs(crossTrackError(coord1, coord2, coord3)) / distanceThreshold;
380
381                        weight = (!closed && i == len - 1) || // don't remove last node of the not closed way
382                                nodeGluesWays(prevNode) ||
383                                angleWeight > 1.0 || areaWeight > 1.0 || distanceWeight > 1.0 ? Double.POSITIVE_INFINITY :
384                                angleWeight * angleFactor + areaWeight * areaFactor + distanceWeight * distanceFactor;
385
386                        weightList.set(prevIndex, weight);
387                    } else {
388                        weight = weightList.get(prevIndex);
389                    }
390
391                    if (weight < minWeight) {
392                        minWeight = weight;
393                        bestMatch = prevNode;
394                    }
395                }
396
397                coord1 = coord2;
398                coord2 = coord3;
399                prevNode = n;
400                prevIndex = index;
401            }
402
403            if (bestMatch == null) {
404                break;
405            }
406
407            final int index = nodes.indexOf(bestMatch);
408
409            weightList.set((index - 1 + size2) % size2, null);
410            weightList.set((index + 1 + size2) % size2, null);
411            weightList.remove(index);
412            nodes.remove(index);
413        }
414
415        final HashSet<Node> delNodes = new HashSet<>(w.getNodes());
416        delNodes.removeAll(nodes);
417
418        nodesToDelete.addAll(delNodes);
419    }
420
421    public static double computeConvectAngle(final LatLon coord1, final LatLon coord2, final LatLon coord3) {
422        final double angle =  Math.abs(heading(coord2, coord3) - heading(coord1, coord2));
423        return Math.toDegrees(angle < Math.PI ? angle : 2 * Math.PI - angle);
424    }
425
426    public static double computeArea(final LatLon coord1, final LatLon coord2, final LatLon coord3) {
427        final double a = coord1.greatCircleDistance(coord2);
428        final double b = coord2.greatCircleDistance(coord3);
429        final double c = coord3.greatCircleDistance(coord1);
430
431        final double p = (a + b + c) / 2.0;
432
433        final double q = p * (p - a) * (p - b) * (p - c); // I found this negative in one case (:-o) when nodes were in line on a small area
434        return q < 0.0 ? 0.0 : Math.sqrt(q);
435    }
436
437    public static double R = 6378135;
438
439    public static double crossTrackError(final LatLon l1, final LatLon l2, final LatLon l3) {
440        return R * Math.asin(sin(l1.greatCircleDistance(l2) / R) * sin(heading(l1, l2) - heading(l1, l3)));
441    }
442
443    public static double heading(final LatLon a, final LatLon b) {
444        double hd = Math.atan2(sin(toRadians(a.lon() - b.lon())) * cos(toRadians(b.lat())),
445                cos(toRadians(a.lat())) * sin(toRadians(b.lat())) -
446                sin(toRadians(a.lat())) * cos(toRadians(b.lat())) * cos(toRadians(a.lon() - b.lon())));
447        hd %= 2 * Math.PI;
448        if (hd < 0) {
449            hd += 2 * Math.PI;
450        }
451        return hd;
452    }
453
454    @Override
455    protected void updateEnabledState() {
456        if (getLayerManager().getEditDataSet() == null) {
457            setEnabled(false);
458        } else {
459            updateEnabledState(getLayerManager().getEditDataSet().getSelected());
460        }
461    }
462
463    @Override
464    protected void updateEnabledState(final Collection<? extends OsmPrimitive> selection) {
465        setEnabled(selection != null && !selection.isEmpty());
466    }
467}
Note: See TracBrowser for help on using the repository browser.