[mkgmap-dev] Error in distance calculations

Wed Dec 24 10:27:56 GMT 2014

Hi programmers,

we are using a formular to calculate the shortest distance
between a point P and a line segment A-B (A,B, and P are coordinates)
The result is either the distance between P and A or P and B or 
the perpendicular distance between the closest point on the 
line A-B and P. In the current code that we use to find out what case we have
we are using the deltas of the garmin lat/lon values.
This formular completely ignores the fact that
we have coordinaties on a sphere (well, nearly a sphere).
The distance between two points with the same deltaLat and deltaLong
is very different depending on the position on the earth,
the farer away from the equator the longer the distance.

The effect of the error is that HousenumberGenerator sometimes
fails to find the right road segment for a housenumber,
and probably the DouglasPeuckerFilter sometimes removes the wrong
points.

The algos I am talking about:
HousenumberGenerator.getFrac()
HousenumberGenerator.distanceToSegment()
and 
Coord.shortestDistToLineSegment() which is more or less a copy of the above.

Up to now I found only one computation that seems to work:
http://stackoverflow.com/questions/1299567/how-to-calculate-distance-from-a-point-to-a-line-segment-on-a-sphere
and esp. parts of the code from here:
https://github.com/Epsidon/PhoneGapExperiments/blob/master/Data/src/DistanceAlgorithm.java

The problem: This algo uses a lot of trigonometric functions to calculate
the result (convert to and from cartesian coordinates) , so it is ~30 times slower.
We do this computation very often in HousenumberGenerator
and DouglasPeuckerFilter.

Is anybody aware of a better compromise between calculation speed and error?

Gerd

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20141224/652329e9/attachment.html>