logo separator

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

From Mark Burton markb at ordern.com on Wed May 20 08:35:41 BST 2009

Hi Wolfgang,

> > Well, that's a good question. As distance() mostly gets called to
> > determine which of a bunch of points is nearest, it probably doesn't
> > matter at all that the result is slightly "wrong".
> 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

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. In terms of performance, I think the new quickDistance() is not
so bad now (at least when compared to the performance of
slowDistance()) and if you look at the java jprof output it no longer
dominates so the gain achieved by using a method such as suggested
above may not be so great.

Of course, we could use a slower, more accurate, function for those
calculations that really would benefit from the increased accuracy and
a "quick and dirty" function for everywhere else.



More information about the mkgmap-dev mailing list