graphhopper / graphhopper/graphhopper
Use DistancePlaneProjection for edge distance calculation in OSMReader
- Dominant language
- Java
- Stars
- 6.7k
- Forks
- 2k
- Avg merge
- 15h 58m
- Merged PRs (30d)
- 3
Description
We currently use DistanceCalcEarth (Haversine formula) in OSMReader to compute edge distances at import time, but both the A* heuristic (BeelineSimplification) and QueryGraph virtual edges already use DistancePlaneProjection. This means stored edge distances and query-time distances are computed with different formulas — a virtual edge from snapping doesn't match the original edge it was split from. We should use DistancePlaneProjection in OSMReader too, so all distances are consistent. This should include EdgeElevationInterpolator etc. that recalculate the edge distance
DistancePlaneProjection always overestimates DistanceCalcEarth, but difference is very small, except for very long east-west segments (when going north-south they are identical):
| lat \ dist | 1km | 5km | 10km | 100km | 500km | 1000km |
|------------|-------|-------|-------|--------|--------|--------|
| 0° | <1mm | <1mm | <1mm | <1mm | <1mm | <1mm |
| 15° | <1mm | <1mm | <1mm | 73.7mm | 9.2m | 73.4m |
| 30° | <1mm | <1mm | <1mm | 342mm | 42.7m | 341m |
| 45° | <1mm | <1mm | 1.0mm | 1.0m | 128m | 1.0km |
| 50° | <1mm | <1mm | 1.7mm | 1.7m | 207m | 1.6km |
| 60° | <1mm | <1mm | 3.1mm | 3.1m | 384m | 3.0km |
| 75° | <1mm | 3.6mm | 14.3mm| 14.3m | 1.8km | 13.4km |
| 85° | <1mm | 33.5mm| 134mm| 134m | 14.4km | 78.0km |
I looked at all edge segment of a planet import to see how much the distances would change if we used DistancePlaneProjection. Out of 2.17 billion segments, only 435 had an absolute difference exceeding 1 meter, and only 172 exceeded 10 meters. These were exclusively very long ferry/shipping segments (100-1300km). The single worst case was a 4500km Pacific ferry segment with 46km absolute difference. Only 2 segments had a relative difference exceeding 0.1%, and the maximum relative error across the entire planet was 1.02% (again the Pacific ferry). For the 99.97% of segments shorter than 1km, the difference is below 0.001mm. No segment shorter than ~170km has a difference exceeding 1 meter. So the only downside of switching to dist_plane is that some (less than 10) very long ferry connections would be 0.1% off the "correct" great circle distance, and two such ferries off up to 1%. Considering that these ferry distances are only very rough estimates of the actual ferry routes, and often we don't have exact travel times for ferries (let alone waiting times etc.) this should not make a difference at all.
```
Total segments: 2171519483
=== Segment length distribution ===
<1m 1460504 ( 0.1%)
1-5m 134329544 ( 6.2%) #########
5-10m 329905223 ( 15.2%) ######################
10-25m 721689018 ( 33.2%) ##################################################
25-50m 505623049 ( 23.3%) ###################################
50-100m 303118032 ( 14.0%) #####################
100-250m 141147528 ( 6.5%) #########
250-500m 25551441 ( 1.2%) #
500-1km 6856078 ( 0.3%)
1-5km 1812758 ( 0.1%)
5-10km 17982 ( 0.0%)
>10km 8326 ( 0.0%)
=== Absolute error distribution (mm) ===
<0.001mm 2170435068 (100.0%) ##################################################
0.001-0.01mm 956340 ( 0.0%)
0.01-0.1mm 108355 ( 0.0%)
0.1-1mm 13773 ( 0.0%)
1-10mm 3354 ( 0.0%)
10-100mm 1425 ( 0.0%)
100mm-1m 733 ( 0.0%)
1-10m 263 ( 0.0%)
>10m 172 ( 0.0%)
=== Relative error distribution (%) ===
<1e-10% 1674617655 ( 77.1%) ##################################################
1e-10-1e-8% 483187067 ( 22.3%) ##############
1e-8-1e-6% 13664105 ( 0.6%)
1e-6-1e-4% 48975 ( 0.0%)
1e-4-0.01% 1606 ( 0.0%)
0.01-0.1% 67 ( 0.0%)
0.1-1% 7 ( 0.0%)
1-10% 1 ( 0.0%)
>10% 0 ( 0.0%)
```
Contributor guide
Assessment
This issue has not been assessed yet.