Repository: graphhopper/graphhopper
Pull request #1042 (2017-04-27 05:49:32)

Replaced Math.atan2 with atan2 table lookup implementation. 
I changed the atan2 implementation of the AngleCalc to a TableLookup version that was provided by @karussell in https://github.com/graphhopper/graphhopper/commit/d64ab7b.

I compared the current master with this version using VisualVM. I used car with ch=fastest. Using the current master, It seems that the `AngleCalc.calcOrientation` was in the Top 10 of CPU time consuming methods of the overall route calculation. With the updated atan2 implementation `AngleCalc.calcOrientation` does not show up in the top 20 CPU time consuming method calls anymore. So it seems to me that this might fix the delay discussed in #1031.

The new atan2 implementation returns slightly different values to `Math.atan2`. I could not find any issues though. I needed to fix two tests. Also I had to add %360 operation, as with the new atan2 implementation we are returning 360 instead of 0. Tests expect 0, so I figured it might be better to do a modulo here instead of changing the tests and maybe introducing a bug in the code.

karussell: Would you do the comparison with the measurement script? (and an area with size like bavaria or saxonia). Then you can look into concrete numbers like `routingCH.mean` and `routingCH_no_instr.mean` for with and without this change.

I'm not sure if we should use it always, especially since we'd export this slightly wrong value to external consumers (Java/JSON API) for roundabouts (RoundaboutInstruction.setRadian)

> Also I had to add %360 operation, as with the new atan2 implementation we are returning 360 instead of 0

Should we do the modulo operation for the root calcOrientation instead?
boldtrn: Here are the results of the measurement, I used: `./graphhopper.sh measurement baden-wuerttemberg-latest.osm.pbf`. I ran it two times for every branch, master and speedup. There is a speedup, but it seems like that it is not the 20% we are looking for.

| Runs         | routingCH.mean | routingCH_no_instr.mean  |
| ------------- |:-------------:| -----:|
| speedup 1 | 2.4596033764 | 1.838547689 |
| master 1 | 2.58897116 | 1.7966665841999998 |
| speedup 2 | 2.305940648 | 1.6758486566 |
| master 2 | 2.4005281016 | 1.7010407452 |

> I'm not sure if we should use it always, especially since we'd export this slightly wrong value to external consumers (Java/JSON API) for roundabouts (RoundaboutInstruction.setRadian)

I can create create a parameter for the calcOrientation method like `exact` that is true per default, using a wrapper method, so no existing code gets broken. 

> Should we do the modulo operation for the root calcOrientation instead?

Mhm, might not be that easy. The case where it returns 360, is when calcOrientation returns a value slightly smaller than 0, like -.0000000000000001. That way we call `Math.toDegrees((2 * Math.PI) - .0000000000000001)` which returns 360.
karussell: > There is a speedup, but it seems like that it is not the 20% we are looking for.

Indeed there is a speedup and I think there are further possibilities.

BTW: strange that you get such different values for the different runs. If you close all other applications and do two runs there shouldn't be a bigger difference than 5%

> Mhm, might not be that easy.

ok
karussell: I investigated a bit further and when doing the angle calculation for *every* junction in the old code (https://github.com/graphhopper/graphhopper/commit/951b443) it got ~15% slower which is still ~5% faster than the state with this PR but explains a big part of the slow down. We could do some pre-calculation on import for the angle stuff, but for now I think this is ok. 

Maybe you can have a second look if we avoid the loop in getOtherContinue over the edges leading to many tan2 calculations calls? And if not possible we keep it as it is with this PR and just introduce an exact=true parameter for the RoundaboutInstruction.setRadian

BTW: we currently do not cache the fetchWayGeometry calls (also many calls via getPointForOrientationCalculation), but temporarily replacing this with a fixed PointList did not speed up anything
BTW: line 213 looks very similar to the code in getPointForOrientationCalculation
boldtrn: > BTW: line 213 looks very similar to the code in getPointForOrientationCalculation

Yes, but it does different things. Putting the logic into the `getPointForOrientationCalculation` is not worth the effort IMHO.

> Maybe you can have a second look if we avoid the loop in getOtherContinue over the edges leading to many tan2 calculations calls?

I spent some time thinking about this a bit more. I came up with a [heuristic](https://github.com/boldtrn/graphhopper/commit/235df5a4fc71d43ee5842dfba1c4f27202bb79c9) that is a lot faster, but actually provides worse results, also a couple of tests fail. The idea is to use the current edge and use its point for orientation calculation as reference. Then we take the point for orientation calculation of the other edge and project it on a straight line to be equal distance than the other point. We then compare the distance between the points and the distance of the point to the base, if the points are closer to each other than to the base, this could be a continue. It might be easier to just read the code ;). So if we need speed, this could be used, but I wouldn't recommend it, as the results are worse. 

I think the best would be to keep it as is and simply add the exact flag.
boldtrn: I forgot to add that the heuristic got about 10% speedup for ch with measurement and Baden-Württemberg, but before investing more time we should remeasure this as I only did one rin. Maybe somebody has a good idea on how to improve it, as the speedup might be worth it. 
karussell: > Putting the logic into the getPointForOrientationCalculation is not worth the effort IMHO.

ok

> I think the best would be to keep it as is and simply add the exact flag.

:+1: 
boldtrn: Ok, I added the exact flag, to make sure that we are actually doing the right thing, I reran the performance measures.

Master: routingCH.mean=2.426111127 routingCH_no_instr.mean=1.7078601832
PR: routingCH.mean=2.2701361754000002 routingCH_no_instr.mean=1.7059984101999999

Patch:
diff --git a/core/src/main/java/com/graphhopper/routing/InstructionsHelper.java b/core/src/main/java/com/graphhopper/routing/InstructionsHelper.java
index 6408371a9..daebfb954 100644
--- a/core/src/main/java/com/graphhopper/routing/InstructionsHelper.java
+++ b/core/src/main/java/com/graphhopper/routing/InstructionsHelper.java
@@ -30,7 +30,7 @@ import com.graphhopper.util.shapes.GHPoint;
 class InstructionsHelper {
 
     static double calculateOrientationDelta(double prevLatitude, double prevLongitude, double latitude, double longitude, double prevOrientation) {
-        double orientation = Helper.ANGLE_CALC.calcOrientation(prevLatitude, prevLongitude, latitude, longitude);
+        double orientation = Helper.ANGLE_CALC.calcOrientation(prevLatitude, prevLongitude, latitude, longitude, false);
         orientation = Helper.ANGLE_CALC.alignOrientation(prevOrientation, orientation);
         return orientation - prevOrientation;
     }
diff --git a/core/src/main/java/com/graphhopper/util/AngleCalc.java b/core/src/main/java/com/graphhopper/util/AngleCalc.java
index 211a4f671..b780f0ee7 100644
--- a/core/src/main/java/com/graphhopper/util/AngleCalc.java
+++ b/core/src/main/java/com/graphhopper/util/AngleCalc.java
@@ -52,15 +52,23 @@ public class AngleCalc {
         return angle;
     }
 
+    public double calcOrientation(double lat1, double lon1, double lat2, double lon2) {
+        return calcOrientation(lat1, lon1, lat2, lon2, true);
+    }
+
     /**
      * Return orientation of line relative to east.
      * <p>
      *
+     * @param exact If false the atan gets calculated faster, but it might contain small errors
      * @return Orientation in interval -pi to +pi where 0 is east
      */
-    public double calcOrientation(double lat1, double lon1, double lat2, double lon2) {
+    public double calcOrientation(double lat1, double lon1, double lat2, double lon2, boolean exact) {
         double shrinkFactor = cos(toRadians((lat1 + lat2) / 2));
-        return Math.atan2(lat2 - lat1, shrinkFactor * (lon2 - lon1));
+        if (exact)
+            return Math.atan2(lat2 - lat1, shrinkFactor * (lon2 - lon1));
+        else
+            return atan2(lat2 - lat1, shrinkFactor * (lon2 - lon1));
     }
 
     /**
@@ -107,7 +115,7 @@ public class AngleCalc {
         if (orientation < 0)
             orientation += 2 * Math.PI;
 
-        return Math.toDegrees(Helper.round4(orientation));
+        return Math.toDegrees(Helper.round4(orientation))%360;
     }
 
     String azimuth2compassPoint(double azimuth) {


Test patch:
diff --git a/core/src/test/java/com/graphhopper/util/AngleCalcTest.java b/core/src/test/java/com/graphhopper/util/AngleCalcTest.java
index 485b57594..1e57838a6 100644
--- a/core/src/test/java/com/graphhopper/util/AngleCalcTest.java
+++ b/core/src/test/java/com/graphhopper/util/AngleCalcTest.java
@@ -29,7 +29,7 @@ public class AngleCalcTest {
     private final AngleCalc AC = Helper.ANGLE_CALC;
 
     @Test
-    public void testOrientation() {
+    public void testOrientationExact() {
         assertEquals(90.0, Math.toDegrees(AC.calcOrientation(0, 0, 1, 0)), 0.01);
         assertEquals(45.0, Math.toDegrees(AC.calcOrientation(0, 0, 1, 1)), 0.01);
         assertEquals(0.0, Math.toDegrees(AC.calcOrientation(0, 0, 0, 1)), 0.01);
@@ -41,6 +41,19 @@ public class AngleCalcTest {
         assertEquals(-90 - 32.76, Math.toDegrees(AC.calcOrientation(49.944, 11.582, 49.942, 11.580)), 0.01);
     }
 
+    @Test
+    public void testOrientationFast() {
+        assertEquals(90.0, Math.toDegrees(AC.calcOrientation(0, 0, 1, 0, false)), 0.01);
+        assertEquals(45.0, Math.toDegrees(AC.calcOrientation(0, 0, 1, 1, false)), 0.01);
+        assertEquals(0.0, Math.toDegrees(AC.calcOrientation(0, 0, 0, 1, false)), 0.01);
+        assertEquals(-45.0, Math.toDegrees(AC.calcOrientation(0, 0, -1, 1, false)), 0.01);
+        assertEquals(-135.0, Math.toDegrees(AC.calcOrientation(0, 0, -1, -1, false)), 0.01);
+
+        // is symetric?
+        assertEquals(90 - 32.92, Math.toDegrees(AC.calcOrientation(49.942, 11.580, 49.944, 11.582, false)), 0.01);
+        assertEquals(-90 - 32.92, Math.toDegrees(AC.calcOrientation(49.944, 11.582, 49.942, 11.580, false)), 0.01);
+    }
+
     @Test
     public void testAlignOrientation() {
         assertEquals(90.0, Math.toDegrees(AC.alignOrientation(Math.toRadians(90), Math.toRadians(90))), 0.001);