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-... and esp. parts of the code from here: https://github.com/Epsidon/PhoneGapExperiments/blob/master/Data/src/Distance... 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
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@hotmail.com To: mkgmap-dev@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-... and esp. parts of the code from here: https://github.com/Epsidon/PhoneGapExperiments/blob/master/Data/src/Distance... 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@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Gerd, I think your calculations are OK for small distances. You could check latitude spread and switch to more complex calculations, similarly like you have for distance() function. -- Best regards, Andrzej
Hi Andrzej, yes, that's what I've done in the patch. I have to do some more checks before I commit that. Gerd
Date: Wed, 24 Dec 2014 13:52:41 +0100 From: popej@poczta.onet.pl To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] Error in distance calculations
Hi Gerd,
I think your calculations are OK for small distances.
You could check latitude spread and switch to more complex calculations, similarly like you have for distance() function.
-- Best regards, Andrzej _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
participants (2)
-
Andrzej Popowski -
Gerd Petermann