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] route recalculation senstivity bug found
Change line 170 of src/uk/me/parabola/imgfmt/app/trergn/TREHeader.java to output 0x170401 instead of 0x110301. I'm happy to try this but won't be able to report back for a few days So I finally got chance to try this out and after a brief test I would say that at best it's the same as current trunk and at worst slightly worse than current but there's really very little in it and my results are subjective not scientific. Hope that helps someone Cheers Paul ___ 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] Filters for overview map
Hi Johann, first some introduction to the overview map: It's only used in mapsource. If you have multiple tiles (for different areas) there is exactly one polygon (rectangle) for each tile. The name for the polygon is the name of the tile plus its map name (the eight digit name). It has a resolution of about 13 (shiftlevel 11). One unit length is on the order of km. The map in that tile usually has a much better resolution, even at its worst level. So the rectangles of the overview map have to be unaligned to the borders of the tile. On Tue, Jun 16, 2009 at 12:03:52AM +0200, Johann Gail wrote: [...] In general i find it an good idea to split up a problem into small parts, but at the moment I cant see the whole thing. Why is it neccessary break things down to smaller rectangles to get an improvement in alignment? Yes, I have seen this error and up to now i thought, there was some rounding error in it. It's rounding errors, yes. And rounding trickery. The problem exists mainly with very small tiles. One can either try to massively enlarge it before the SizeFilter kicks in, or get it with an acceptable size, which could be (1 x 1) units^2 in the relevant resolution. It's on the order of km, so a 1x1 rect is still large. In my testing it turned out, that the SizeFilter and the DouglasPeuckerFilter either dropped my small rectangles or converted them to a triangle. Removing the filters fixed this for me. If you think, that the generated rectangles should be large enough, so that they're not cleaned: - If this is so, then there really is no reason for calling the filters anyway, they should be NOPs in that case. So we can optimize them away. My opinioin: I dont know the special case for the overview map. On a normal map layer I dont assume that all elements are large enough. If an element is to small to be displayed then we can drop it completely. If you drop one polygon, the reference to one tile is dropped, which finally means, that this tile is not displayed at all by mapsource. We may not drop a single polygon, because we want to show all tiles in mapsource. - I hope to show in later patches (don't hold your breath! I will go slowly step by step. There is no need to hurry anyway) that smaller rects might make some sense. As said before, I dont know the complete background. Maybe with the overview map it is reasonable to not drop the indisplayable things. It's not indisplayable. The resolution is just very bad, even for zooming in to meters. It's just containing the borders of the map tiles. So it doesn't really need better resolution. [...] With this patch you introduce the possibility to disable filtering. I see nothing destructed, but (at the moment) no use in it. But if I understand it correctly, then the filtering is switched of for the complete overview map layer. Wouldn't that increase file size a lot? I would expect at this resolution a lot of filtered small streets. As said above, there are no streets or anything else in the overview map. More important: Does it increase redrawing speed at low zoom levels, which is possibly the main use of a overview map? Or is the overview map not used at the gps unit? It's only used by mapsource. It's only generated if you call with --tdbfile. The main intention for the douglas peucker filter was the low drawing speed on my etrex handheld at low zoom levels. Don't be discouraged by my critics. It are only my thoughts at the moment. Regards, Johann ___ 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] Filters for overview map
Hi, My current conclusions from both thread parts: 1) I should only disable the SizeFilter (we really, really don't want to drop any polygon). 2) We should fix DP. Does that make sense? Elrond ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Filters for overview map
Hi, Am 16.06.2009 um 20:39 schrieb Elrond: My current conclusions from both thread parts: 1) I should only disable the SizeFilter (we really, really don't want to drop any polygon). For the overview map obviously not. 2) We should fix DP. From what you explained about the overview map (I was always wondering what it is for...) also DP for the overview map makes no sense. What would make sense though would be to split the tiles in a way that the polygons in the overview map need no rounding. Or is that already the case? And yes, we should fix DP (if it is actually broken). 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
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] Filters for overview map
Hi, On Tue, Jun 16, 2009 at 10:49:45PM +0200, Thilo Hannemann wrote: Hi, Am 16.06.2009 um 20:39 schrieb Elrond: My current conclusions from both thread parts: 1) I should only disable the SizeFilter (we really, really don't want to drop any polygon). For the overview map obviously not. 2) We should fix DP. From what you explained about the overview map (I was always wondering what it is for...) also DP for the overview map makes no sense. I read that as You can commit this. I'll wait for a little for possible other input. :) What would make sense though would be to split the tiles in a way that the polygons in the overview map need no rounding. Or is that already the case? Hmmm, maybe my naming was bad. With tile I meant a region as defined by the boundaries in the foo.osm you're using to create one map. So the boundaries are really set by the user. And getting those boundaries close to the overviewmap-alignment is not easy (for the user). The alignment edges change with the center of the world (the overview map). So in short: I don't see a simple way for doing it. Splitting at the map level would require mkgmap to auto-select new (eight digit) map names for the newly created maps. And this splitting can only happen, when/if the world is known, so quite too late. We'd need two-pass handling or so. And yes, we should fix DP (if it is actually broken). I only noticed it for the overview map. So I can't really tell, if it is broken or not. I just have speculated on its cause in the other thread part. Regards Thilo Elrond ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
