[mkgmap-dev] Overview map: tiny patch/review series

Tue Jun 16 16:15:51 BST 2009

Hi Mark,

Am 16.06.2009 um 09:18 schrieb Mark Burton:

> At the distances we're (mostly) interested in, the curvature of the
> earth's surface has a tiny effect (much less than the effect of  
> hills &
> valleys) so I guess (hope) that leaving out that factor is OK.

The curvature may have a tiny effect, but nonetheless you should  
consider the coordinate system you are using. Interpreting lat and lon  
as cartesian coordinates (don't know whether you are really doing  
that) will give large errors at high latitudes.

> I know that this isn't your code but it's as good a place as any
> to comment about it: looking at the DP code (for the first time), I
> immediately see that the loop that finds the max distance is
> (potentially) doing many more sqrts and divisions than it needs to. So
> even if the code is correct, it could be somewhat faster which would  
> be
> worthwhile given that it gets called for every line. Eg, it could be
> changed to look like this:
>
> 		// Find point with highest distance.
> 		// Loop runs downwards, as the list length gets modified while  
> running
> 		for(int i = endIndex-1; i > startIndex; i--) {
> 			Coord p = points.get(i);
> 			double ap = p.distance(a);
> 			double bp = p.distance(b);
> 			double abpa = (ab+ap+bp)/2;
> 			double dd = abpa * (abpa-ab) * (abpa-ap) * (abpa-bp);
> 			if (dd > maxDistance) {
> 				maxDistance = dd;
> 				maxIndex = i;
> 			}
> 		}
> 		maxDistance = 2 * Math.sqrt(maxDistance) / ab;
>
> Also - you get a division by zero if ab is 0, perhaps adding a test
> for that before the loop would be advisable.

Do you understand that formula for the distance calculation? If so  
could you explain it for me? I don't get it.

> Another minor nit - the comment is inaccurate as the list length  
> doesn't change in this loop.

It is accurate, because the list length does get changed by the way  
the recursion works. It is not obvious, therefore this comment is  
really needed!

Another question, just out of curiosity: Does it really mattern in  
Java how many sqrts or sin or cos I do? Doesn't that kind of  
difference get swamped by all that interpretation and memory  
allocation things etc. going on? With modern FPUs that kind of  
operation isn't that expensive (if it is done native).

I would start working on the DP code if it makes sense. If somebody  
understands that distance formula and could explain it it would be  
very much appreciated. Otherwise I will have to make up my own formula  
(sigh...)

Regards
Thilo