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