[mkgmap-dev] [PATCH v1] quick distance calculation

Wed May 20 09:44:29 BST 2009

On Wed, 20 May 2009, Mark Burton wrote:

>> Really? In that case you could as well change the metric from Euclidean 
>> to something more simple like the Manhattan metric:
>>
>>    dist = abs(lat2-lat1) + costab[lat1] * abs(lon2-lon1)
>>
>> where costab is a table lookup for cos(). This will still find a point 
>> that is close, but it is not guaranteed to be the same as with the 
>> Euclidean metric. Would that matter?
>
> Good question. Unfortunately, my maths is not so good so I can't answer 
> it.

This is not a question of maths but of the requirements of the algorithm: 
Do you need "a close" or "the closest" point?

> Absolute distance measurement is still required in a couple of places so 
> we don't want to give up too much accuracy for the sake of speed.

I would suggest to retain the original distance() for all places where the 
exact distance is needed and to define approximateDistance() for other 
cases -- either using your current implementation or something 
minimalistic like my proposal depending on the requirements.

-Wolfgang

PS: If it's just for finding nearest neighbours, you can improve the 
performance of your code by
1. Working in map units (no conversion)
2. Replacing the if-blocks by Math.abs() or the ternary "? :"-operator
3. Computing the cosine by table lookup
4. Removing sqrt to compute squared distances
5. Removing scale factors for the output