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.
This is correct. The algorithm does not depend on the lat and long
values. It doesn't work with the internal units. This units are locally
like kartesian coordinates but with changing scales.
Therfore I call the function distance(), which I expect to return
distance values in the unit m independent of the lan/lot of the points.
The triangle of the points could be seen as nearly flat. So the distance
calculation should not return any significant errors.
It should calculate the distance of a point to the line.
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.
Yes, I have thought about some optimasations, but not had the right
idea. I find it a good idea to extract the sqrt() from the loop or even
better compare the value to the squared allowedError.
But on the other hand it makes the formula a little more complicated and
even more programmers ask about the function of it....
I length of zero should not be possible at this point, as it would mean
two points with the same coordintates. This are filtered out in a
previous stage. But you are correct, some assertion would be a good idea.
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...
Very well explained. Now I understand the distance formula too :-)
I'm not a mathematician too, but I found this formula on some web page
and testing it with some example values shows me, that it works correctly.
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).
You were correct. At this place the comment is wrong.
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!
Yes, the code was from me, but I have only sporadically time for this
mailing list. So if some important questions arive, write to the list.
But I cannot garantee fast answer.
Regards,
Johann
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
