Changeset 15574 in josm

Timestamp:

2019-12-09T09:47:20+01:00 (6 years ago)

Author:

GerdP

Message:

fix #18367 and #18385: CombineWayAction (C) refuses to combine ways or silently reverses ways
Changes:

• try first to combine the ways with the method Multipolygon.joinWays() If that method returns a single line string we can use it, else use the result of NodeGraph.buildSpanningPathNoRemove(). Both methods will not add or remove segments
• if ways are combined execute checks for overlapping segments or self-intersection and show a notification popup right after the command was added to the UndoRedoHandler
• The code which handles reversed ways needed changes. In the unpatched version it sometimes claims wrongly that ways were reversed, in special cases it sometimes silently reverted ways. The old code did not handle the case properly that a node can appear more than once. I really hope that I got it right now.
• Fix some sonarlint issues
• let NodeGraph routines return an ArrayList instead of a LinkedList (improves performance a bit)
• Add unit tests

Location:

trunk

Files:

• src/org/openstreetmap/josm/actions/CombineWayAction.java (modified) (7 diffs)
• src/org/openstreetmap/josm/data/osm/NodeGraph.java (modified) (5 diffs)
• test/data/regress/18367 (added)
• test/data/regress/18367/nocombine.osm (added)
• test/data/regress/18367/silent-revert.osm (added)
• test/data/regress/18367/split-and-reverse.osm (added)
• test/unit/org/openstreetmap/josm/actions/CombineWayActionTest.java (modified) (6 diffs)

trunk/src/org/openstreetmap/josm/actions/CombineWayAction.java

@@ -32 +32 @@
 import org.openstreetmap.josm.data.osm.TagCollection;
 import org.openstreetmap.josm.data.osm.Way;
+import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon;
+import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.JoinedWay;
 import org.openstreetmap.josm.data.preferences.BooleanProperty;
+import org.openstreetmap.josm.data.validation.Test;
+import org.openstreetmap.josm.data.validation.tests.OverlappingWays;
+import org.openstreetmap.josm.data.validation.tests.SelfIntersectingWay;
 import org.openstreetmap.josm.gui.ExtendedDialog;
 import org.openstreetmap.josm.gui.MainApplication;
@@ -123 +128 @@
 
         // try to build a new way which includes all the combined ways
-        NodeGraph graph = NodeGraph.createNearlyUndirectedGraphFromNodeWays(ways);
-        List<Node> path = graph.buildSpanningPathNoRemove();
-        if (path == null) {
+        List<Node> path = tryJoin(ways);
+        if (path.isEmpty()) {
             warnCombiningImpossible();
             return null;
@@ -137 +141 @@
         List<Way> reversedWays = new LinkedList<>();
         List<Way> unreversedWays = new LinkedList<>();
-        for (Way w: ways) {
-            // Treat zero or one-node ways as unreversed as Combine action action is a good way to fix them (see #8971)
-            if (w.getNodesCount() < 2 || (path.indexOf(w.getNode(0)) + 1) == path.lastIndexOf(w.getNode(1))) {
-                unreversedWays.add(w);
-            } else {
-                reversedWays.add(w);
-            }
-        }
+        detectReversedWays(ways, path, reversedWays, unreversedWays);
         // reverse path if all ways have been reversed
         if (unreversedWays.isEmpty()) {
@@ -164 +161 @@
             }
             // if there are still reversed ways with direction-dependent tags, reverse their tags
-            if (!reversedWays.isEmpty() && PROP_REVERSE_WAY.get()) {
+            if (!reversedWays.isEmpty() && Boolean.TRUE.equals(PROP_REVERSE_WAY.get())) {
                 List<Way> unreversedTagWays = new ArrayList<>(ways);
                 unreversedTagWays.removeAll(reversedWays);
@@ -211 +208 @@
 
         return new Pair<>(targetWay, sequenceCommand);
+    }
+
+    protected static void detectReversedWays(Collection<Way> ways, List<Node> path, List<Way> reversedWays,
+            List<Way> unreversedWays) {
+        for (Way w: ways) {
+            // Treat zero or one-node ways as unreversed as Combine action action is a good way to fix them (see #8971)
+            if (w.getNodesCount() < 2) {
+                unreversedWays.add(w);
+            } else {
+                boolean foundStartSegment = false;
+                int last = path.lastIndexOf(w.getNode(0));
+
+                for (int i = path.indexOf(w.getNode(0)); i <= last; i++) {
+                    if (path.get(i) == w.getNode(0) && i + 1 < path.size() && w.getNode(1) == path.get(i + 1)) {
+                        foundStartSegment = true;
+                        break;
+                    }
+                }
+                if (foundStartSegment) {
+                    unreversedWays.add(w);
+                } else {
+                    reversedWays.add(w);
+                }
+            }
+        }
+    }
+
+    protected static List<Node> tryJoin(Collection<Way> ways) {
+        List<Node> path = joinWithMultipolygonCode(ways);
+        if (path.isEmpty()) {
+            NodeGraph graph = NodeGraph.createNearlyUndirectedGraphFromNodeWays(ways);
+            path = graph.buildSpanningPathNoRemove();
+        }
+        return path;
+    }
+
+    /**
+     * Use {@link Multipolygon#joinWays(Collection)} to join ways.
+     * @param ways the ways
+     * @return List of nodes of the combined ways or null if ways could not be combined to a single way.
+     * Result may contain overlapping segments.
+     */
+    private static List<Node> joinWithMultipolygonCode(Collection<Way> ways) {
+        // sort so that old unclosed ways appear first
+        LinkedList<Way> toJoin = new LinkedList<>(ways);
+        toJoin.sort((o1, o2) -> {
+            int d = Boolean.compare(o1.isNew(), o2.isNew());
+            if (d == 0)
+                d = Boolean.compare(o1.isClosed(), o2.isClosed());
+            return d;
+        });
+        Collection<JoinedWay> list = Multipolygon.joinWays(toJoin);
+        if (list.size() == 1) {
+            // ways form a single line string
+            return new ArrayList<>(list.iterator().next().getNodes());
+        }
+        return Collections.emptyList();
     }
 
@@ -238 +292 @@
         if (combineResult == null)
             return;
+
         final Way selectedWay = combineResult.a;
         UndoRedoHandler.getInstance().add(combineResult.b);
+        Test test = new OverlappingWays();
+        test.startTest(null);
+        test.visit(combineResult.a);
+        test.endTest();
+        if (test.getErrors().isEmpty()) {
+            test = new SelfIntersectingWay();
+            test.startTest(null);
+            test.visit(combineResult.a);
+            test.endTest();
+        }
+        if (!test.getErrors().isEmpty()) {
+            new Notification(test.getErrors().get(0).getMessage())
+            .setIcon(JOptionPane.WARNING_MESSAGE)
+            .setDuration(Notification.TIME_SHORT)
+            .show();
+        }
         if (selectedWay != null) {
             GuiHelper.runInEDT(() -> ds.setSelected(selectedWay));
@@ -262 +333 @@
         setEnabled(numWays >= 2);
     }
+
 }

trunk/src/org/openstreetmap/josm/data/osm/NodeGraph.java

@@ -12 +12 @@
 import java.util.LinkedHashMap;
 import java.util.LinkedHashSet;
-import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
@@ -18 +17 @@
 import java.util.Optional;
 import java.util.Set;
-import java.util.Stack;
 import java.util.TreeMap;
 
@@ -249 +247 @@
     }
 
-    protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
-        List<Node> ret = new LinkedList<>();
-        for (NodePair pair: path) {
+    protected List<Node> buildPathFromNodePairs(Deque<NodePair> path) {
+        List<Node> ret = new ArrayList<>(path.size() + 1);
+        for (NodePair pair : path) {
             ret.add(pair.getA());
         }
-        ret.add(path.peek().getB());
+        ret.add(path.peekLast().getB());
         return ret;
     }
@@ -264 +262 @@
      *
      * @param startNode the start node
-     * @return the spanning path; null, if no path is found
+     * @return the spanning path; empty list if no path is found
      */
     protected List<Node> buildSpanningPath(Node startNode) {
         if (startNode != null) {
-            // do not simply replace `Stack` by `ArrayDeque` because of different iteration behaviour, see #11957
-            Stack<NodePair> path = new Stack<>();
+            Deque<NodePair> path = new ArrayDeque<>();
             Set<NodePair> dupCheck = new HashSet<>();
-            Stack<NodePair> nextPairs = new Stack<>();
+            Deque<NodePair> nextPairs = new ArrayDeque<>();
             nextPairs.addAll(getOutboundPairs(startNode));
             while (!nextPairs.isEmpty()) {
-                NodePair cur = nextPairs.pop();
+                NodePair cur = nextPairs.removeLast();
                 if (!dupCheck.contains(cur) && !dupCheck.contains(cur.swap())) {
-                    while (!path.isEmpty() && !path.peek().isPredecessorOf(cur)) {
-                        dupCheck.remove(path.pop());
+                    while (!path.isEmpty() && !path.peekLast().isPredecessorOf(cur)) {
+                        dupCheck.remove(path.removeLast());
                     }
-                    path.push(cur);
+                    path.addLast(cur);
                     dupCheck.add(cur);
-                    if (isSpanningWay(path)) return buildPathFromNodePairs(path);
-                    nextPairs.addAll(getOutboundPairs(path.peek()));
+                    if (isSpanningWay(path))
+                        return buildPathFromNodePairs(path);
+                    nextPairs.addAll(getOutboundPairs(path.peekLast()));
                 }
             }
@@ -324 +322 @@
      * any duplicated edge was removed.
      *
-     * @return the path; null, if no path was found or duplicated edges were found
-     * @since 15555
+     * @return List of nodes that build the path; an empty list if no path or duplicated edges were found
+     * @since 15573 (return value not null)
      */
     public List<Node> buildSpanningPathNoRemove() {
-        if (edges.size() != addedEdges)
-            return null;
-        return buildSpanningPath();
+        List<Node> path = null;
+        if (edges.size() == addedEdges)
+            path = buildSpanningPath();
+        return path == null ? Collections.emptyList() : path;
     }
 

trunk/test/unit/org/openstreetmap/josm/actions/CombineWayActionTest.java

@@ -3 +3 @@
 
 import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertNull;
-import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.assertFalse;
 
 import java.io.IOException;
 import java.io.InputStream;
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.Collections;
 import java.util.HashSet;
+import java.util.LinkedList;
 import java.util.List;
 import java.util.Set;
@@ -19 +20 @@
 import org.openstreetmap.josm.data.osm.DataSet;
 import org.openstreetmap.josm.data.osm.Node;
-import org.openstreetmap.josm.data.osm.NodeGraph;
 import org.openstreetmap.josm.data.osm.NodePair;
 import org.openstreetmap.josm.data.osm.Way;
@@ -50 +50 @@
         try (InputStream is = TestUtils.getRegressionDataStream(11957, "data.osm")) {
             DataSet ds = OsmReader.parseDataSet(is, null);
-            NodeGraph graph = NodeGraph.createNearlyUndirectedGraphFromNodeWays(ds.getWays());
-            List<Node> path = graph.buildSpanningPathNoRemove();
+            List<Node> path = CombineWayAction.tryJoin(ds.getWays());
             assertEquals(10, path.size());
             Set<Long> firstAndLastObtained = new HashSet<>();
@@ -72 +71 @@
         try (InputStream is = TestUtils.getRegressionDataStream(18385, "data.osm")) {
             DataSet ds = OsmReader.parseDataSet(is, null);
-            NodeGraph graph = NodeGraph.createNearlyUndirectedGraphFromNodeWays(ds.getWays());
-            List<Node> path = graph.buildSpanningPathNoRemove();
-            assertNull(path);
+            List<Node> path = CombineWayAction.tryJoin(ds.getWays());
+            assertFalse(path.isEmpty());
         }
     }
@@ -91 +89 @@
             if (!selection.get(0).isNew())
                 Collections.reverse(selection);
-            NodeGraph graph = NodeGraph.createNearlyUndirectedGraphFromNodeWays(selection);
-            List<Node> path = graph.buildSpanningPathNoRemove();
-            assertTrue(path != null);
+            double expectedLen = getOriginalLength(selection);
+            List<Node> path = CombineWayAction.tryJoin(selection);
+            assertFalse(path.isEmpty());
+            Way combined = new Way(0);
+            combined.setNodes(path);
+            assertEquals(expectedLen, combined.getLength(), 0.01);
         }
     }
+
+    /**
+     * Non-regression test for bug #18367 (Lines cannot be combined when they share an overlapping segment)
+     * @throws IOException if any I/O error occurs
+     * @throws IllegalDataException if OSM parsing fails
+     */
+    @Test
+    public void testTicket18367() throws IOException, IllegalDataException {
+        try (InputStream is = TestUtils.getRegressionDataStream(18367, "nocombine.osm")) {
+            DataSet ds = OsmReader.parseDataSet(is, null);
+            ArrayList<Way> selection = new ArrayList<>(ds.getWays());
+            assertEquals(2, selection.size());
+            double expectedLen = getOriginalLength(selection);
+            List<Node> path = CombineWayAction.tryJoin(selection);
+            assertFalse(path.isEmpty());
+            Way combined = new Way(0);
+            combined.setNodes(path);
+            assertEquals(expectedLen, combined.getLength(), 1e-7);
+        }
+    }
+
+
+    /**
+     * Non-regression test for bug #18367
+     * @throws IOException if any I/O error occurs
+     * @throws IllegalDataException if OSM parsing fails
+     */
+    @Test
+    public void testTicket18367NeedsSplit() throws IOException, IllegalDataException {
+        try (InputStream is = TestUtils.getRegressionDataStream(18367, "split-and-reverse.osm")) {
+            DataSet ds = OsmReader.parseDataSet(is, null);
+            ArrayList<Way> selection = new ArrayList<>(ds.getWays());
+            assertEquals(2, selection.size());
+            double expectedLen = getOriginalLength(selection);
+            List<Node> path = CombineWayAction.tryJoin(selection);
+            assertFalse(path.isEmpty());
+            Way combined = new Way(0);
+            combined.setNodes(path);
+            assertEquals(expectedLen, combined.getLength(), 1e-7);
+            List<Way> reversedWays = new LinkedList<>();
+            List<Way> unreversedWays = new LinkedList<>();
+            CombineWayAction.detectReversedWays(selection, path, reversedWays, unreversedWays);
+            assertFalse(reversedWays.isEmpty());
+        }
+    }
+
+
+    /**
+     * Test for bad reverse way detection. See #18367
+     * @throws IOException if any I/O error occurs
+     * @throws IllegalDataException if OSM parsing fails
+     */
+    @Test
+    public void testDetectReversedWays() throws IOException, IllegalDataException {
+        try (InputStream is = TestUtils.getRegressionDataStream(18367, "silent-revert.osm")) {
+            DataSet ds = OsmReader.parseDataSet(is, null);
+            ArrayList<Way> selection = new ArrayList<>(ds.getWays());
+            assertEquals(2, selection.size());
+            // make sure that short way is first
+            if (selection.get(0).getNodesCount() != 2)
+                Collections.reverse(selection);
+            double expectedLen = getOriginalLength(selection);
+            List<Node> path = CombineWayAction.tryJoin(selection);
+            assertFalse(path.isEmpty());
+            Way combined = new Way(0);
+            combined.setNodes(path);
+            assertEquals(expectedLen, combined.getLength(), 1e-7);
+            List<Way> reversedWays = new LinkedList<>();
+            List<Way> unreversedWays = new LinkedList<>();
+            CombineWayAction.detectReversedWays(selection, path, reversedWays, unreversedWays);
+            assertFalse(reversedWays.contains(selection.get(0)));
+        }
+    }
+
 
     /**
@@ -107 +182 @@
             .verify();
     }
+
+    private static double getOriginalLength(Collection<Way> ways) {
+        double len = 0;
+        for (Way w : ways) {
+            len += w.getLength();
+        }
+        return len;
+    }
+
 }