<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 12pt;
font-family:Calibri
}
--></style></head>
<body class='hmmessage'><div dir='ltr'>Hi,<br><br>I think I found what I searched for.<br>With the attached patch I get fast results which are close<br>to the results of the slow algo.<br><br>Gerd<br><br><div><hr id="stopSpelling">From: gpetermann_muenchen@hotmail.com<br>To: mkgmap-dev@lists.mkgmap.org.uk<br>Date: Wed, 24 Dec 2014 11:27:56 +0100<br>Subject: [mkgmap-dev] Error in distance calculations<br><br>

<style><!--
.ExternalClass .ecxhmmessage P {
padding:0px;
}

.ExternalClass body.ecxhmmessage {
font-size:12pt;
font-family:Calibri;
}

--></style>
<div dir="ltr">Hi programmers,<br><br>we are using a formular to calculate the shortest distance<br>between a point P and a line segment A-B (A,B, and P are coordinates)<br>The result is either the distance between P and A or P and B or <br>the perpendicular distance between the closest point on the <br>line A-B and P. In the current code that we use to find out what case we have<br>we are using the deltas of the garmin lat/lon values.<br>This formular completely ignores the fact that<br>we have coordinaties on a sphere (well, nearly a sphere).<br>The distance between two points with the same deltaLat and deltaLong<br>is very different depending on the position on the earth,<br>the farer away from the equator the longer the distance.<br><br>The effect of the error is that HousenumberGenerator sometimes<br>fails to find the right road segment for a housenumber,<br>and probably the DouglasPeuckerFilter sometimes removes the wrong<br>points.<br><br>The algos I am talking about:<br>HousenumberGenerator.getFrac()<br>HousenumberGenerator.distanceToSegment()<br>and <br>Coord.shortestDistToLineSegment() which is more or less a copy of the above.<br><br>Up to now I found only one computation that seems to work:<br><a href="http://stackoverflow.com/questions/1299567/how-to-calculate-distance-from-a-point-to-a-line-segment-on-a-sphere" target="_blank">http://stackoverflow.com/questions/1299567/how-to-calculate-distance-from-a-point-to-a-line-segment-on-a-sphere</a><br>and esp. parts of the code from here:<br><a href="https://github.com/Epsidon/PhoneGapExperiments/blob/master/Data/src/DistanceAlgorithm.java" target="_blank">https://github.com/Epsidon/PhoneGapExperiments/blob/master/Data/src/DistanceAlgorithm.java</a><br><br>The problem: This algo uses a lot of trigonometric functions to calculate<br>the result (convert to and from cartesian coordinates) , so it is ~30 times slower.<br>We do this computation very often in HousenumberGenerator<br>and DouglasPeuckerFilter.<br><br>Is anybody aware of a better compromise between calculation speed and error?<br><br>Gerd<br><br><br><br><br><br>                                               </div>
<br>_______________________________________________
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev</div>                                               </div></body>
</html>