Changeset 15574 in josm


Ignore:
Timestamp:
2019-12-09T09:47:20+01:00 (4 months 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:
4 added
3 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/org/openstreetmap/josm/actions/CombineWayAction.java

    r15555 r15574  
    3232import org.openstreetmap.josm.data.osm.TagCollection;
    3333import org.openstreetmap.josm.data.osm.Way;
     34import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon;
     35import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.JoinedWay;
    3436import org.openstreetmap.josm.data.preferences.BooleanProperty;
     37import org.openstreetmap.josm.data.validation.Test;
     38import org.openstreetmap.josm.data.validation.tests.OverlappingWays;
     39import org.openstreetmap.josm.data.validation.tests.SelfIntersectingWay;
    3540import org.openstreetmap.josm.gui.ExtendedDialog;
    3641import org.openstreetmap.josm.gui.MainApplication;
     
    123128
    124129        // try to build a new way which includes all the combined ways
    125         NodeGraph graph = NodeGraph.createNearlyUndirectedGraphFromNodeWays(ways);
    126         List<Node> path = graph.buildSpanningPathNoRemove();
    127         if (path == null) {
     130        List<Node> path = tryJoin(ways);
     131        if (path.isEmpty()) {
    128132            warnCombiningImpossible();
    129133            return null;
     
    137141        List<Way> reversedWays = new LinkedList<>();
    138142        List<Way> unreversedWays = new LinkedList<>();
    139         for (Way w: ways) {
    140             // Treat zero or one-node ways as unreversed as Combine action action is a good way to fix them (see #8971)
    141             if (w.getNodesCount() < 2 || (path.indexOf(w.getNode(0)) + 1) == path.lastIndexOf(w.getNode(1))) {
    142                 unreversedWays.add(w);
    143             } else {
    144                 reversedWays.add(w);
    145             }
    146         }
     143        detectReversedWays(ways, path, reversedWays, unreversedWays);
    147144        // reverse path if all ways have been reversed
    148145        if (unreversedWays.isEmpty()) {
     
    164161            }
    165162            // if there are still reversed ways with direction-dependent tags, reverse their tags
    166             if (!reversedWays.isEmpty() && PROP_REVERSE_WAY.get()) {
     163            if (!reversedWays.isEmpty() && Boolean.TRUE.equals(PROP_REVERSE_WAY.get())) {
    167164                List<Way> unreversedTagWays = new ArrayList<>(ways);
    168165                unreversedTagWays.removeAll(reversedWays);
     
    211208
    212209        return new Pair<>(targetWay, sequenceCommand);
     210    }
     211
     212    protected static void detectReversedWays(Collection<Way> ways, List<Node> path, List<Way> reversedWays,
     213            List<Way> unreversedWays) {
     214        for (Way w: ways) {
     215            // Treat zero or one-node ways as unreversed as Combine action action is a good way to fix them (see #8971)
     216            if (w.getNodesCount() < 2) {
     217                unreversedWays.add(w);
     218            } else {
     219                boolean foundStartSegment = false;
     220                int last = path.lastIndexOf(w.getNode(0));
     221
     222                for (int i = path.indexOf(w.getNode(0)); i <= last; i++) {
     223                    if (path.get(i) == w.getNode(0) && i + 1 < path.size() && w.getNode(1) == path.get(i + 1)) {
     224                        foundStartSegment = true;
     225                        break;
     226                    }
     227                }
     228                if (foundStartSegment) {
     229                    unreversedWays.add(w);
     230                } else {
     231                    reversedWays.add(w);
     232                }
     233            }
     234        }
     235    }
     236
     237    protected static List<Node> tryJoin(Collection<Way> ways) {
     238        List<Node> path = joinWithMultipolygonCode(ways);
     239        if (path.isEmpty()) {
     240            NodeGraph graph = NodeGraph.createNearlyUndirectedGraphFromNodeWays(ways);
     241            path = graph.buildSpanningPathNoRemove();
     242        }
     243        return path;
     244    }
     245
     246    /**
     247     * Use {@link Multipolygon#joinWays(Collection)} to join ways.
     248     * @param ways the ways
     249     * @return List of nodes of the combined ways or null if ways could not be combined to a single way.
     250     * Result may contain overlapping segments.
     251     */
     252    private static List<Node> joinWithMultipolygonCode(Collection<Way> ways) {
     253        // sort so that old unclosed ways appear first
     254        LinkedList<Way> toJoin = new LinkedList<>(ways);
     255        toJoin.sort((o1, o2) -> {
     256            int d = Boolean.compare(o1.isNew(), o2.isNew());
     257            if (d == 0)
     258                d = Boolean.compare(o1.isClosed(), o2.isClosed());
     259            return d;
     260        });
     261        Collection<JoinedWay> list = Multipolygon.joinWays(toJoin);
     262        if (list.size() == 1) {
     263            // ways form a single line string
     264            return new ArrayList<>(list.iterator().next().getNodes());
     265        }
     266        return Collections.emptyList();
    213267    }
    214268
     
    238292        if (combineResult == null)
    239293            return;
     294
    240295        final Way selectedWay = combineResult.a;
    241296        UndoRedoHandler.getInstance().add(combineResult.b);
     297        Test test = new OverlappingWays();
     298        test.startTest(null);
     299        test.visit(combineResult.a);
     300        test.endTest();
     301        if (test.getErrors().isEmpty()) {
     302            test = new SelfIntersectingWay();
     303            test.startTest(null);
     304            test.visit(combineResult.a);
     305            test.endTest();
     306        }
     307        if (!test.getErrors().isEmpty()) {
     308            new Notification(test.getErrors().get(0).getMessage())
     309            .setIcon(JOptionPane.WARNING_MESSAGE)
     310            .setDuration(Notification.TIME_SHORT)
     311            .show();
     312        }
    242313        if (selectedWay != null) {
    243314            GuiHelper.runInEDT(() -> ds.setSelected(selectedWay));
     
    262333        setEnabled(numWays >= 2);
    263334    }
     335
    264336}
  • trunk/src/org/openstreetmap/josm/data/osm/NodeGraph.java

    r15559 r15574  
    1212import java.util.LinkedHashMap;
    1313import java.util.LinkedHashSet;
    14 import java.util.LinkedList;
    1514import java.util.List;
    1615import java.util.Map;
     
    1817import java.util.Optional;
    1918import java.util.Set;
    20 import java.util.Stack;
    2119import java.util.TreeMap;
    2220
     
    249247    }
    250248
    251     protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
    252         List<Node> ret = new LinkedList<>();
    253         for (NodePair pair: path) {
     249    protected List<Node> buildPathFromNodePairs(Deque<NodePair> path) {
     250        List<Node> ret = new ArrayList<>(path.size() + 1);
     251        for (NodePair pair : path) {
    254252            ret.add(pair.getA());
    255253        }
    256         ret.add(path.peek().getB());
     254        ret.add(path.peekLast().getB());
    257255        return ret;
    258256    }
     
    264262     *
    265263     * @param startNode the start node
    266      * @return the spanning path; null, if no path is found
     264     * @return the spanning path; empty list if no path is found
    267265     */
    268266    protected List<Node> buildSpanningPath(Node startNode) {
    269267        if (startNode != null) {
    270             // do not simply replace `Stack` by `ArrayDeque` because of different iteration behaviour, see #11957
    271             Stack<NodePair> path = new Stack<>();
     268            Deque<NodePair> path = new ArrayDeque<>();
    272269            Set<NodePair> dupCheck = new HashSet<>();
    273             Stack<NodePair> nextPairs = new Stack<>();
     270            Deque<NodePair> nextPairs = new ArrayDeque<>();
    274271            nextPairs.addAll(getOutboundPairs(startNode));
    275272            while (!nextPairs.isEmpty()) {
    276                 NodePair cur = nextPairs.pop();
     273                NodePair cur = nextPairs.removeLast();
    277274                if (!dupCheck.contains(cur) && !dupCheck.contains(cur.swap())) {
    278                     while (!path.isEmpty() && !path.peek().isPredecessorOf(cur)) {
    279                         dupCheck.remove(path.pop());
     275                    while (!path.isEmpty() && !path.peekLast().isPredecessorOf(cur)) {
     276                        dupCheck.remove(path.removeLast());
    280277                    }
    281                     path.push(cur);
     278                    path.addLast(cur);
    282279                    dupCheck.add(cur);
    283                     if (isSpanningWay(path)) return buildPathFromNodePairs(path);
    284                     nextPairs.addAll(getOutboundPairs(path.peek()));
     280                    if (isSpanningWay(path))
     281                        return buildPathFromNodePairs(path);
     282                    nextPairs.addAll(getOutboundPairs(path.peekLast()));
    285283                }
    286284            }
     
    324322     * any duplicated edge was removed.
    325323     *
    326      * @return the path; null, if no path was found or duplicated edges were found
    327      * @since 15555
     324     * @return List of nodes that build the path; an empty list if no path or duplicated edges were found
     325     * @since 15573 (return value not null)
    328326     */
    329327    public List<Node> buildSpanningPathNoRemove() {
    330         if (edges.size() != addedEdges)
    331             return null;
    332         return buildSpanningPath();
     328        List<Node> path = null;
     329        if (edges.size() == addedEdges)
     330            path = buildSpanningPath();
     331        return path == null ? Collections.emptyList() : path;
    333332    }
    334333
  • trunk/test/unit/org/openstreetmap/josm/actions/CombineWayActionTest.java

    r15558 r15574  
    33
    44import static org.junit.Assert.assertEquals;
    5 import static org.junit.Assert.assertNull;
    6 import static org.junit.Assert.assertTrue;
     5import static org.junit.Assert.assertFalse;
    76
    87import java.io.IOException;
    98import java.io.InputStream;
    109import java.util.ArrayList;
     10import java.util.Collection;
    1111import java.util.Collections;
    1212import java.util.HashSet;
     13import java.util.LinkedList;
    1314import java.util.List;
    1415import java.util.Set;
     
    1920import org.openstreetmap.josm.data.osm.DataSet;
    2021import org.openstreetmap.josm.data.osm.Node;
    21 import org.openstreetmap.josm.data.osm.NodeGraph;
    2222import org.openstreetmap.josm.data.osm.NodePair;
    2323import org.openstreetmap.josm.data.osm.Way;
     
    5050        try (InputStream is = TestUtils.getRegressionDataStream(11957, "data.osm")) {
    5151            DataSet ds = OsmReader.parseDataSet(is, null);
    52             NodeGraph graph = NodeGraph.createNearlyUndirectedGraphFromNodeWays(ds.getWays());
    53             List<Node> path = graph.buildSpanningPathNoRemove();
     52            List<Node> path = CombineWayAction.tryJoin(ds.getWays());
    5453            assertEquals(10, path.size());
    5554            Set<Long> firstAndLastObtained = new HashSet<>();
     
    7271        try (InputStream is = TestUtils.getRegressionDataStream(18385, "data.osm")) {
    7372            DataSet ds = OsmReader.parseDataSet(is, null);
    74             NodeGraph graph = NodeGraph.createNearlyUndirectedGraphFromNodeWays(ds.getWays());
    75             List<Node> path = graph.buildSpanningPathNoRemove();
    76             assertNull(path);
     73            List<Node> path = CombineWayAction.tryJoin(ds.getWays());
     74            assertFalse(path.isEmpty());
    7775        }
    7876    }
     
    9189            if (!selection.get(0).isNew())
    9290                Collections.reverse(selection);
    93             NodeGraph graph = NodeGraph.createNearlyUndirectedGraphFromNodeWays(selection);
    94             List<Node> path = graph.buildSpanningPathNoRemove();
    95             assertTrue(path != null);
     91            double expectedLen = getOriginalLength(selection);
     92            List<Node> path = CombineWayAction.tryJoin(selection);
     93            assertFalse(path.isEmpty());
     94            Way combined = new Way(0);
     95            combined.setNodes(path);
     96            assertEquals(expectedLen, combined.getLength(), 0.01);
    9697        }
    9798    }
     99
     100    /**
     101     * Non-regression test for bug #18367 (Lines cannot be combined when they share an overlapping segment)
     102     * @throws IOException if any I/O error occurs
     103     * @throws IllegalDataException if OSM parsing fails
     104     */
     105    @Test
     106    public void testTicket18367() throws IOException, IllegalDataException {
     107        try (InputStream is = TestUtils.getRegressionDataStream(18367, "nocombine.osm")) {
     108            DataSet ds = OsmReader.parseDataSet(is, null);
     109            ArrayList<Way> selection = new ArrayList<>(ds.getWays());
     110            assertEquals(2, selection.size());
     111            double expectedLen = getOriginalLength(selection);
     112            List<Node> path = CombineWayAction.tryJoin(selection);
     113            assertFalse(path.isEmpty());
     114            Way combined = new Way(0);
     115            combined.setNodes(path);
     116            assertEquals(expectedLen, combined.getLength(), 1e-7);
     117        }
     118    }
     119
     120
     121    /**
     122     * Non-regression test for bug #18367
     123     * @throws IOException if any I/O error occurs
     124     * @throws IllegalDataException if OSM parsing fails
     125     */
     126    @Test
     127    public void testTicket18367NeedsSplit() throws IOException, IllegalDataException {
     128        try (InputStream is = TestUtils.getRegressionDataStream(18367, "split-and-reverse.osm")) {
     129            DataSet ds = OsmReader.parseDataSet(is, null);
     130            ArrayList<Way> selection = new ArrayList<>(ds.getWays());
     131            assertEquals(2, selection.size());
     132            double expectedLen = getOriginalLength(selection);
     133            List<Node> path = CombineWayAction.tryJoin(selection);
     134            assertFalse(path.isEmpty());
     135            Way combined = new Way(0);
     136            combined.setNodes(path);
     137            assertEquals(expectedLen, combined.getLength(), 1e-7);
     138            List<Way> reversedWays = new LinkedList<>();
     139            List<Way> unreversedWays = new LinkedList<>();
     140            CombineWayAction.detectReversedWays(selection, path, reversedWays, unreversedWays);
     141            assertFalse(reversedWays.isEmpty());
     142        }
     143    }
     144
     145
     146    /**
     147     * Test for bad reverse way detection. See #18367
     148     * @throws IOException if any I/O error occurs
     149     * @throws IllegalDataException if OSM parsing fails
     150     */
     151    @Test
     152    public void testDetectReversedWays() throws IOException, IllegalDataException {
     153        try (InputStream is = TestUtils.getRegressionDataStream(18367, "silent-revert.osm")) {
     154            DataSet ds = OsmReader.parseDataSet(is, null);
     155            ArrayList<Way> selection = new ArrayList<>(ds.getWays());
     156            assertEquals(2, selection.size());
     157            // make sure that short way is first
     158            if (selection.get(0).getNodesCount() != 2)
     159                Collections.reverse(selection);
     160            double expectedLen = getOriginalLength(selection);
     161            List<Node> path = CombineWayAction.tryJoin(selection);
     162            assertFalse(path.isEmpty());
     163            Way combined = new Way(0);
     164            combined.setNodes(path);
     165            assertEquals(expectedLen, combined.getLength(), 1e-7);
     166            List<Way> reversedWays = new LinkedList<>();
     167            List<Way> unreversedWays = new LinkedList<>();
     168            CombineWayAction.detectReversedWays(selection, path, reversedWays, unreversedWays);
     169            assertFalse(reversedWays.contains(selection.get(0)));
     170        }
     171    }
     172
    98173
    99174    /**
     
    107182            .verify();
    108183    }
     184
     185    private static double getOriginalLength(Collection<Way> ways) {
     186        double len = 0;
     187        for (Way w : ways) {
     188            len += w.getLength();
     189        }
     190        return len;
     191    }
     192
    109193}
Note: See TracChangeset for help on using the changeset viewer.