Re: [mkgmap-dev] Overview map: tiny patch/review series
Hi Mark, Am 16.06.2009 um 08:33 schrieb Mark Burton: Recently, Coord.distance() was replaced with a much speedier implementation because a lot of cpu cycles were being wasted there. The newer function appears to be accurate enough for our purposes. The DP code contains another distance calculation. What you must calculate there is the distance of one point to a line. The Coord.distance() is used in that formula, but I do not understand the formula itself. Maybe it's some genius trick to simplify the calculation, but I do not get it. The only thing I see is that when I reduce the error distance the simplified ways look nicer. But the preset error distance of one half of the resolution should be small enough already. So my assumption is that the actual error distance is much larger than expected, which may be due to a bug in the code. Regards Thilo ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Overview map: tiny patch/review series
Hi Thilo,
The DP code contains another distance calculation. What you must
calculate there is the distance of one point to a line. The
Coord.distance() is used in that formula, but I do not understand the
formula itself. Maybe it's some genius trick to simplify the
calculation, but I do not get it. The only thing I see is that when I
reduce the error distance the simplified ways look nicer. But the
preset error distance of one half of the resolution should be small
enough already. So my assumption is that the actual error distance is
much larger than expected, which may be due to a bug in the code.
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.
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.
Another minor nit - the comment is inaccurate as the list length doesn't change
in this loop.
Cheers,
Mark
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Overview map: tiny patch/review series
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
Re: [mkgmap-dev] Overview map: tiny patch/review series
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
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Overview map: tiny patch/review series
On Tue, 16 Jun 2009 17:19:21 +0100 Mark Burton ma...@ordern.com wrote: 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. Well, a quick test showed a barely perceptible gain so may as well leave the code as it is. Cheers, Mark ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Overview map: tiny patch/review series
--- 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
Re: [mkgmap-dev] Overview map: tiny patch/review series
On Tue, Jun 16, 2009 at 07:58:24AM +0200, Thilo Hannemann wrote: Hi Elrond, [...] The problem of distorted polygons does not only appear in the overview map, it appears at all zoom levels. [...] Hi, Okay, about the DP code, I have some speculation, why it performs bad. It's a variation on what happens for the overview map in general. Rounding. Okay, let me make up an example. Let's assume, that current resolution will round to full units (you might think degree). And lets assume mathematical rounding (1.4 - 1, 1.5 - 2) A: (0.2, 2.4) B: (1.2, 2.4) C: (1.2, 2.5) so the bare inter-vectors are: A-B: (1.0, 0.0) B-C: (0.0, 0.2) Looking at that, it seems, that B is not far off from A-C. So we drop B. Now let's see, what the rounding makes out of the whole story: a = round(A): (0, 2) b = round(B): (1, 2) c = round(C): (1, 3) So for not dropping B: a-b: (1, 0) b-c: (0, 1) For dropping B: a-c: (1, 1) The distance of b to a-c is sqrt(2)/2 (0.707), so more than unit/2. Greetings Elrond ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Overview map: tiny patch/review series
Am 16.06.2009 um 18:33 schrieb Marco Certelli: 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... You are right. It is Heron's formula. And from what I see the implementation is correct. Even the coordinates on the sphere are no problem, because the formula itself doesn't use lat and lon and we can assume the triangle to be flat locally. So I think the implementation is quite clever indeed. Okay. But that still doesn't explain why the map looks better if I reduce the error distance setting for the Douglas-Peucker filter. The error should be already invisible at the default setting. Regards Thilo ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Overview map: tiny patch/review series
Hi Elrond, there seem to be some problems with the simplification right now. But instead of simply de-activating the simplification I think we should debug the code. Of course it's fine to de-activate it for debugging :) The problem of distorted polygons does not only appear in the overview map, it appears at all zoom levels. One problem I could identify is that the Douglas-Peucker code does remove the closing node of a polygon, but doesn't put it back after simplification. This might be ok for filled polygons, but for contour lines it is a problem. I've attached the patch that I use to solve that problem. decrease_douglas_peucker_error.patch Description: Binary data That patch also sets the error distance for the Douglas-Peucker algorithm to 1/8th of the resolution instead of one half. In my opinion this gives much nicer results. The question here is why it is so, because you shouldn't be able to see such small errors. From looking at the Douglas-Peucker code I can not put my finger on any bug. What I do not understand is the distance calculation. Anybody with insight cares to have a look at it (or explain how it works?). I'd assume that a distance calculation on a spherical surface would involve lots of trigonometric functions - which the formula in the code doesn't. Take care Thilo ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
