--- Mar 16/6/09, Mark Burton <ma...@ordern.com> ha scritto:
> Da: Mark Burton <ma...@ordern.com>
> Oggetto: Re: [mkgmap-dev] Overview map: tiny patch/review series
> A: mkgmap-dev@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@lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev