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

Tue Jun 16 17:19:21 BST 2009

Hi Thilo,

> > 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 have to admit that I'm not much of a mathematician so I am quite
happy to take advice as to the soundness of the current algorithm. I
did test it against what we were using before and for the latitudes I
was using, it appeared to work OK.

> > 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.

Sorry, no.

> 
> > 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!

The loop I mention does not contain any recursion. The loop in
doFilter() does (it is adorned with a similar comment).

> 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).

You're quite possibly right but some maths ops are hideously slow (i.e.
acos which is used in the original distance() method). In the example
above, I would argue that taking the sqrt and division outside of the
loop doesn't make the code harder to understand and may yield some
speedup. 

> 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...)

Well, I think Johann wrote the code so maybe he will enlighten you!

Cheers,

Mark