[mkgmap-dev] Error in distance calculations

Wed Dec 24 10:59:38 GMT 2014

Hi,

I think I found what I searched for.
With the attached patch I get fast results which are close
to the results of the slow algo.

Gerd

From: gpetermann_muenchen at hotmail.com
To: mkgmap-dev at lists.mkgmap.org.uk
Date: Wed, 24 Dec 2014 11:27:56 +0100
Subject: [mkgmap-dev] Error in distance calculations

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

_______________________________________________
mkgmap-dev mailing list
mkgmap-dev at lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev 		 	   		  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20141224/1a09fe3b/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: distToSegment-v1.patch
Type: application/octet-stream
Size: 827 bytes
Desc: not available
URL: <http://www.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20141224/1a09fe3b/attachment.obj>