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
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
