Skip to content

Experiment: Azimuth computation optimization

Andrew Byrd edited this page Dec 17, 2014 · 1 revision

During profiling of spatial index queries, we realized that a very large percentage of the time spent in getClosestEdges() was spend computing azimuth in the CandidateEdge constructor.

The azimuth function from Geotools is an exact one but is really expensive: see here, it use an iterative process to get the result.

We replaced it with an approximated version, using a simpler and faster Math.atan2() on an equirectangular projection.

In term of performances, the new approximated version is more than 10 times faster than the exact one:

Benchmark for 1000000 computations:
- 5535 ms for the exact version
- 375 ms for the approximate version.

It's not exact for long distances, but since the result is used for getting a drive "snap score" on the candidate edge, computing a turn factor or displaying absolute direction to the user, it won't matter that much. For small lengths (typical for street segment) the error is really negligible, it only become noticeable for several hundreds of kms.

One side effect is that now azimuth computation is correct on the pole (going from the north pole to any other point is indeed going SOUTH), there is a bug in the geotools implementation.

The documentation on this wiki is outdated and should not be used

unless you are intentionally working with legacy versions of OpenTripPlanner. Please consult the current documentation at readthedocs

Clone this wiki locally