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

Tue Jun 16 17:33:51 BST 2009

--- Mar 16/6/09, Mark Burton <markb at ordern.com> ha scritto:

> Da: Mark Burton <markb at ordern.com>
> Oggetto: Re: [mkgmap-dev] Overview map: tiny patch/review series
> A: mkgmap-dev at lists.mkgmap.org.uk
> Data: Martedì 16 giugno 2009, 18:19
> 
> 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.
> 

Just speculation:

I've a and b that defines a line. I look for the distance between a point p and the line.

Given the triangle p-a-b where p is the vertex and a-b is the "base", the area of the triangle can be calculated from the lenght of its 3 sides (pa, pb, ab).

After that, since the area is also base x height / 2 we can calculate the height = area / base * 2

well, the height is exactly the distance of the point p from the line a-b

Maybe...

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