Repository: graphhopper/graphhopper (java)

Issue:
Instructions: Remove unnecessary slight turns, if the alternative would be a sharp turn
Something that happens frequently is the creation of "slight turns" that are no real turns and users would just follow the road, but since there is another option for a turn, we create a turn instruction.

See this example: https://graphhopper.com/maps/?point=51.734514%2C9.225571&point=51.734643%2C9.22541

We create a "turn slight right" instruction. But this makes no sense. When for example driving [this route](https://graphhopper.com/maps/?point=51.733622%2C9.225914&point=51.735245%2C9.225125), a user could misinterpret the turn slight right instruction and turn right at the intersection like [this](https://graphhopper.com/maps/?point=51.733622%2C9.225914&point=51.73451%2C9.227051).

I think we could improve this situation, by checking if the orientation of the other turn. If the other turn is almost a u-turn (e.g. >140°) it might be ok to omit a turn instruction that is only a slight turn.

This is kind of related to #1007 

WDYT?

Pull request description:
Remove unnecessary slight turns
Fixes #1441. We already had some logic to ignore unnecessary slight turns. I increased the angle to remove more of these examples. This changed the number of instructions in some IT. I had a look at these cases visually and the new version looks better to me. It's a bit hard to do that though, since the test data is quite old, and the map visualization moved on with the current data.

Patch:
diff --git a/core/src/main/java/com/graphhopper/routing/InstructionsFromEdges.java b/core/src/main/java/com/graphhopper/routing/InstructionsFromEdges.java
index 31740967d..02dd8f491 100644
--- a/core/src/main/java/com/graphhopper/routing/InstructionsFromEdges.java
+++ b/core/src/main/java/com/graphhopper/routing/InstructionsFromEdges.java
@@ -286,7 +286,7 @@ public class InstructionsFromEdges implements Path.EdgeVisitor {
                     prevAnnotation = annotation;
                 }
             }
-            // Updated the prevName, since we don't always create an instruction on name changes the previous
+            // Update the prevName, since we don't always create an instruction on name changes the previous
             // name can be an old name. This leads to incorrect turn instructions due to name changes
             prevName = name;
         }
@@ -420,7 +420,7 @@ public class InstructionsFromEdges implements Path.EdgeVisitor {
         }
 
         if (!outgoingEdgesAreSlower) {
-            if (Math.abs(delta) > .4
+            if (Math.abs(delta) > .6
                     || outgoingEdges.isLeavingCurrentStreet(prevName, name)) {
                 // Leave the current road -> create instruction
                 return sign;


Test patch:
diff --git a/core/src/test/java/com/graphhopper/util/InstructionListTest.java b/core/src/test/java/com/graphhopper/util/InstructionListTest.java
index 1a3f23aff..29fa361db 100644
--- a/core/src/test/java/com/graphhopper/util/InstructionListTest.java
+++ b/core/src/test/java/com/graphhopper/util/InstructionListTest.java
@@ -231,6 +231,64 @@ public class InstructionListTest {
         assertEquals(Arrays.asList("continue onto street", "turn right onto street", "arrive at destination"), tmpList);
     }
 
+    @Test
+    public void testNoInstructionIfSlightTurnAndAlternativeIsSharp() {
+        Graph g = new GraphBuilder(carManager).create();
+        // Real World Example: https://graphhopper.com/maps/?point=51.734514%2C9.225571&point=51.734643%2C9.22541
+        // https://github.com/graphhopper/graphhopper/issues/1441
+        // From 1 to 3
+        //
+        //       3
+        //       |
+        //       2
+        //      /\
+        //     4  1
+
+        NodeAccess na = g.getNodeAccess();
+        na.setNode(1, 51.734514,9.225571);
+        na.setNode(2, 51.73458,9.225442);
+        na.setNode(3, 51.734643,9.22541);
+        na.setNode(4, 51.734451,9.225436);
+        g.edge(1, 2, 10, true);
+        g.edge(2, 3, 10, true);
+        g.edge(2, 4, 10, true);
+
+        ShortestWeighting weighting = new ShortestWeighting(carEncoder);
+        Path p = new Dijkstra(g, weighting, tMode).calcPath(1, 3);
+        InstructionList wayList = InstructionsFromEdges.calcInstructions(p, g, weighting, roundaboutEnc, usTR);
+        List<String> tmpList = getTurnDescriptions( wayList);
+        assertEquals(Arrays.asList("continue", "arrive at destination"), tmpList);
+    }
+
+    @Test
+    public void testNoInstructionIfSlightTurnAndAlternativeIsSharp2() {
+        Graph g = new GraphBuilder(carManager).create();
+        // Real World Example: https://graphhopper.com/maps/?point=48.748493%2C9.322455&point=48.748776%2C9.321889
+        // https://github.com/graphhopper/graphhopper/issues/1441
+        // From 1 to 3
+        //
+        //       3
+        //         \
+        //          2--- 1
+        //           \
+        //            4
+
+        NodeAccess na = g.getNodeAccess();
+        na.setNode(1, 48.748493,9.322455);
+        na.setNode(2, 48.748577,9.322152);
+        na.setNode(3, 48.748776,9.321889);
+        na.setNode(4, 48.74847,9.322299);
+        g.edge(1, 2, 10, true);
+        g.edge(2, 3, 10, true);
+        g.edge(2, 4, 10, true);
+
+        ShortestWeighting weighting = new ShortestWeighting(carEncoder);
+        Path p = new Dijkstra(g, weighting, tMode).calcPath(1, 3);
+        InstructionList wayList = InstructionsFromEdges.calcInstructions(p, g, weighting, roundaboutEnc, usTR);
+        List<String> tmpList = getTurnDescriptions( wayList);
+        assertEquals(Arrays.asList("continue", "arrive at destination"), tmpList);
+    }
+
     @Test
     public void testEmptyList() {
         Graph g = new GraphBuilder(carManager).create();
diff --git a/reader-osm/src/test/java/com/graphhopper/GraphHopperIT.java b/reader-osm/src/test/java/com/graphhopper/GraphHopperIT.java
index 336e2af73..cedb82d79 100644
--- a/reader-osm/src/test/java/com/graphhopper/GraphHopperIT.java
+++ b/reader-osm/src/test/java/com/graphhopper/GraphHopperIT.java
@@ -101,7 +101,7 @@ public class GraphHopperIT {
         assertEquals(43.7495432, arsp.getWaypoints().getLat(1), 1e-7);
 
         InstructionList il = arsp.getInstructions();
-        assertEquals(21, il.size());
+        assertEquals(20, il.size());
 
         // TODO roundabout fine tuning -> enter + leave roundabout (+ two roundabouts -> is it necessary if we do not leave the street?)
         Translation tr = hopper.getTranslationMap().getWithFallBack(Locale.US);
@@ -492,22 +492,22 @@ public class GraphHopperIT {
         assertEquals(173, arsp.getPoints().getSize());
 
         InstructionList il = arsp.getInstructions();
-        assertEquals(38, il.size());
+        assertEquals(36, il.size());
         assertEquals("continue onto Avenue des Guelfes", il.get(0).getTurnDescription(tr));
         assertEquals("continue onto Avenue des Papalins", il.get(1).getTurnDescription(tr));
         assertEquals("turn sharp right onto Quai Jean-Charles Rey", il.get(4).getTurnDescription(tr));
         assertEquals("turn left", il.get(5).getTurnDescription(tr));
         assertEquals("turn right onto Avenue Albert II", il.get(6).getTurnDescription(tr));
 
-        assertEquals("waypoint 1", il.get(20).getTurnDescription(tr));
-        assertEquals(Instruction.U_TURN_UNKNOWN, il.get(21).getSign());
+        assertEquals("waypoint 1", il.get(19).getTurnDescription(tr));
+        assertEquals(Instruction.U_TURN_UNKNOWN, il.get(20).getSign());
 
-        assertEquals("continue onto Avenue Albert II", il.get(31).getTurnDescription(tr));
-        assertEquals("turn left", il.get(32).getTurnDescription(tr));
-        assertEquals("turn right onto Quai Jean-Charles Rey", il.get(33).getTurnDescription(tr));
-        assertEquals("turn sharp left onto Avenue des Papalins", il.get(34).getTurnDescription(tr));
-        assertEquals("continue onto Avenue des Guelfes", il.get(36).getTurnDescription(tr));
-        assertEquals("arrive at destination", il.get(37).getTurnDescription(tr));
+        assertEquals("continue onto Avenue Albert II", il.get(29).getTurnDescription(tr));
+        assertEquals("turn left", il.get(30).getTurnDescription(tr));
+        assertEquals("turn right onto Quai Jean-Charles Rey", il.get(31).getTurnDescription(tr));
+        assertEquals("turn sharp left onto Avenue des Papalins", il.get(32).getTurnDescription(tr));
+        assertEquals("continue onto Avenue des Guelfes", il.get(34).getTurnDescription(tr));
+        assertEquals("arrive at destination", il.get(35).getTurnDescription(tr));
 
         assertEquals(11, il.get(0).getDistance(), 1);
         assertEquals(97, il.get(1).getDistance(), 1);
@@ -706,7 +706,7 @@ public class GraphHopperIT {
         assertTrue(arsp.getPoints().is3D());
 
         InstructionList il = arsp.getInstructions();
-        assertEquals(13, il.size());
+        assertEquals(12, il.size());
         assertTrue(il.get(0).getPoints().is3D());
 
         String str = arsp.getPoints().toString();
@@ -813,7 +813,7 @@ public class GraphHopperIT {
         assertEquals(106, arsp.getPoints().getSize());
 
         InstructionList il = arsp.getInstructions();
-        assertEquals(24, il.size());
+        assertEquals(22, il.size());
 
         assertEquals("continue onto Obere Landstraße", il.get(0).getTurnDescription(tr));
         assertEquals("get off the bike", il.get(0).getAnnotation().getMessage());
@@ -830,8 +830,8 @@ public class GraphHopperIT {
         assertEquals("keep left onto Austraße", il.get(11).getTurnDescription(tr));
         assertEquals("keep left onto Rechte Kremszeile", il.get(12).getTurnDescription(tr));
         //..
-        assertEquals("turn right onto Treppelweg", il.get(19).getTurnDescription(tr));
-        assertEquals("cycleway", il.get(19).getAnnotation().getMessage());
+        assertEquals("turn right onto Treppelweg", il.get(18).getTurnDescription(tr));
+        assertEquals("cycleway", il.get(18).getAnnotation().getMessage());
     }
 
     @Test
@@ -1336,16 +1336,16 @@ public class GraphHopperIT {
         final String avenue = "Avenue de la Costa";
         assertCurbsidesPathError(h, p, q, asList(CURBSIDE_RIGHT, CURBSIDE_RIGHT), "Impossible curbside constraint: 'curbside=right' at point 0", true);
         assertCurbsidesPathError(h, p, q, asList(CURBSIDE_RIGHT, CURBSIDE_LEFT), "Impossible curbside constraint: 'curbside=right' at point 0", true);
-        assertCurbsidesPath(h, p, q, asList(CURBSIDE_LEFT, CURBSIDE_RIGHT), 463, asList(boulevard, avenue, avenue));
+        assertCurbsidesPath(h, p, q, asList(CURBSIDE_LEFT, CURBSIDE_RIGHT), 463, asList(boulevard, avenue));
         assertCurbsidesPathError(h, p, q, asList(CURBSIDE_LEFT, CURBSIDE_LEFT), "Impossible curbside constraint: 'curbside=left' at point 1", true);
         // without restricting anything we get the shortest path
-        assertCurbsidesPath(h, p, q, asList(CURBSIDE_ANY, CURBSIDE_ANY), 463, asList(boulevard, avenue, avenue));
-        assertCurbsidesPath(h, p, q, Collections.<String>emptyList(), 463, asList(boulevard, avenue, avenue));
+        assertCurbsidesPath(h, p, q, asList(CURBSIDE_ANY, CURBSIDE_ANY), 463, asList(boulevard, avenue));
+        assertCurbsidesPath(h, p, q, Collections.<String>emptyList(), 463, asList(boulevard, avenue));
         // if we set force_curbside to false impossible curbside constraints will be ignored
-        assertCurbsidesPath(h, p, q, asList(CURBSIDE_RIGHT, CURBSIDE_RIGHT), 463, asList(boulevard, avenue, avenue), false);
-        assertCurbsidesPath(h, p, q, asList(CURBSIDE_RIGHT, CURBSIDE_LEFT), 463, asList(boulevard, avenue, avenue), false);
-        assertCurbsidesPath(h, p, q, asList(CURBSIDE_LEFT, CURBSIDE_RIGHT), 463, asList(boulevard, avenue, avenue), false);
-        assertCurbsidesPath(h, p, q, asList(CURBSIDE_LEFT, CURBSIDE_LEFT), 463, asList(boulevard, avenue, avenue), false);
+        assertCurbsidesPath(h, p, q, asList(CURBSIDE_RIGHT, CURBSIDE_RIGHT), 463, asList(boulevard, avenue), false);
+        assertCurbsidesPath(h, p, q, asList(CURBSIDE_RIGHT, CURBSIDE_LEFT), 463, asList(boulevard, avenue), false);
+        assertCurbsidesPath(h, p, q, asList(CURBSIDE_LEFT, CURBSIDE_RIGHT), 463, asList(boulevard, avenue), false);
+        assertCurbsidesPath(h, p, q, asList(CURBSIDE_LEFT, CURBSIDE_LEFT), 463, asList(boulevard, avenue), false);
     }
 
     private void assertCurbsidesPath(GraphHopper tmpHopper, GHPoint source, GHPoint target, List<String> curbsides, int expectedDistance, List<String> expectedStreets) {
diff --git a/web/src/test/java/com/graphhopper/http/resources/RouteResourceTest.java b/web/src/test/java/com/graphhopper/http/resources/RouteResourceTest.java
index 1aaec00a0..6008f8a02 100644
--- a/web/src/test/java/com/graphhopper/http/resources/RouteResourceTest.java
+++ b/web/src/test/java/com/graphhopper/http/resources/RouteResourceTest.java
@@ -182,11 +182,11 @@ public class RouteResourceTest {
         assertTrue("distance wasn't correct:" + arsp.getDistance(), arsp.getDistance() < 21000);
 
         InstructionList instructions = arsp.getInstructions();
-        assertEquals(26, instructions.size());
+        assertEquals(25, instructions.size());
         assertEquals("Continue onto la Callisa", instructions.get(0).getTurnDescription(null));
         assertEquals("At roundabout, take exit 2", instructions.get(4).getTurnDescription(null));
         assertEquals(true, instructions.get(4).getExtraInfoJSON().get("exited"));
-        assertEquals(false, instructions.get(24).getExtraInfoJSON().get("exited"));
+        assertEquals(false, instructions.get(23).getExtraInfoJSON().get("exited"));
     }
 
     @Test