Overview map: tiny patch/review series
Hi developers, Probably many have already noticed, that the overview map (used to contain the polygons for selecting tiles in mapsource) isn't perfect. Often the polygons are much too large, or sometimes too small. They also feel like having a bias (at least for me). I have tried to fix this. And I think I was successful. After a short talk on irc we concluded: Instead of just commiting stuff, I will post patches here on the ML for review. So that people can give comments before I commit them. This is for mainly two reasons: 1) Some thoughts are not too simple, and I want to make sure, everyone understands them and at the same time, that they're right. 2) Some parts change some internals drastically and I feel, I might have overlooked something in this cause. Elrond
Hi, okay, first part. 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. - 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. So this simple patch disables both filters for the overview map. If nobody objects or I get some "Go", I'll commit it soon. Elrond
Hi,
okay, first part.
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.
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.
- 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.
So this simple patch disables both filters for the overview map.
If nobody objects or I get some "Go", I'll commit it soon.
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. 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? 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
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
Hi Thanks for working out what goes wrong with very small maps. Although you are correct that the overview map only contains area definition and background polygons which should not be dropped, in the future the overview map should contain real map features so it might be best to specifically exclude those polygon types. ..Steve
Ok, thank you for your detailed explanations. From my side you get the okay to get on with your first step :-) Regards, Johann
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
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
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
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. 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
Hi Thilo, I know nothing about the DP code so I can't comment on that. On Tue, 16 Jun 2009 07:58:24 +0200 Thilo Hannemann <thannema@gmx.de> wrote:
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.
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. Cheers, Mark
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
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
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
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
On Tue, 16 Jun 2009 17:19:21 +0100 Mark Burton <markb@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
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
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.
[...] The distance of b to a->c is sqrt(2)/2 (0.707), so more than unit/2.
Yes, I think this could be very well the problem. I don't know at the moment how the coorinates are rounded at higher shift levels, but this could be a very well explanation. If this is the case, it would explain, why it occurs at all shift levels. Get the coordinates rounded to bit size before or after the DP filter? Regards, Johann
Hi everyone, As rounding seems a current topic, I'm throwing in a patch that is sitting in my tree for a while now: We used to round coords to the shifted values in a subdiv by just using the ">>" shift operator. This works. But it's not the mathematical way of rounding, and the later is better IMHO. Let me explain this with an example: Let's assume the center-Lat of a subdiv is exactly at 0. Let's assume the shift-value is 4. So we divide by 16, or truncate to it, however you like to think about it. So if we have a point at lat=31, it will have the shifted value of (31-0) >> 4 = _1_. This will be displayed at 0 + (_1_ << 4) = 16. While _2_ would give us 0 + (_2_ << 4) = 32. 32 is much closer to the real value. Another more intuitive way of looking at the whole thing is with classic rounding: Just assume, that the current shift value is choosen so that we round exactly to "degrees" (some special sort of degrees). So, 3.9 will currently be rounded to just 3, not 4. The solution is add half the rounding distance and truncate: truncate(3.9 + 0.5) = 4. PENDING ISSUES: I am not sure, that I have catched all cases in mkgmap. Any feedback on this is highly welcome. Of course, general testing and feedback is also welcome! Elrond p.s.: This is also related to the overview map issue I was talking about a while back and wanting to post patches for. This one can be counted as the next one.
On Tue, Aug 11, 2009 at 3:50 PM, Elrond<elrond+openstreetmap.org@samba-tng.org> wrote:
As rounding seems a current topic, I'm throwing in a patch that is sitting in my tree for a while now:
How can I best test this patch? Is there something I can look for without examining the binary data of the generated map? (For example, what are typical symptoms of incorrect rounding?) Thanks!
Hi Clinton, On Tue, Aug 11, 2009 at 05:13:04PM +0200, Clinton Gladstone wrote:
On Tue, Aug 11, 2009 at 3:50 PM, Elrond<elrond+openstreetmap.org@samba-tng.org> wrote:
As rounding seems a current topic, I'm throwing in a patch that is sitting in my tree for a while now:
How can I best test this patch? Is there something I can look for without examining the binary data of the generated map? (For example, what are typical symptoms of incorrect rounding?)
"incorrect" is probably too hard (except for the very special case, where I needed the better rounding). "suboptimal" would be a better term. To be honest, I don't know for sure how to really pin-point it. My idea on this: Set mapsource to "low detail" so that you get low resolution data even when zoomed in somewhat. Zoom in until the residential roads just apear and zoom out once (so that they disappear again). That way you get some lower resolution and should be able to see the "raster"-resolution of the points used to make up all the lines. About one fourth should be a little off relative to the others with my patch, I'd say... If you then switch the detail to "highest" to see the data with more resolution but at the same zoom, you should see the differences. Without the patch, maybe a few are farer away from the "real" position than with the patch. I hope this makes some sense to you... Cheers Elrond
On Tue, Aug 11, 2009 at 5:37 PM, Elrond<elrond+openstreetmap.org@samba-tng.org> wrote:
"incorrect" is probably too hard (except for the very special case, where I needed the better rounding). "suboptimal" would be a better term.
Hi Elrond, I tested your patch, and could see differences in the map. However, I could not really determine which would be more 'optimal'. I'll just take your word for that. ;-) (I tested on Roadtrip for the Mac, so behaviour may differ in Mapsource or in a GPS unit.) I have noted no additional difficulties with the patch. Everything seems to work fine so far, both in Roadtrip and on my eTrex. Thanks.
Hi Elrond, hello list, ... I did *not* yet test the patch, but, while biking around with a Garmin this morning, I realised that getting the rounding correct is an improvement, because your position is more precise. This could help in cases where a subtle rounding error will just put you on another road. You won't notice the difference as an end user, because there's many places where the choice of two parallel roads is difficult and any GPS unit will make some mistakes. My guess is that you could only see the difference when you would try to gather data on how many times you are on the right track and how many times you're 0.5 off... So if you ask me, "better rounding is better" and we should use anything that rounds better :) V. Clinton Gladstone schreef:
Elrond<elrond+openstreetmap.org@samba-tng.org> wrote:
"incorrect" is probably too hard (except for the very special case, where I needed the better rounding). "suboptimal" would be a better term. I tested your patch, and could see differences in the map. However, I could not really determine which would be more 'optimal'.
participants (7)
-
Clinton Gladstone -
Elrond -
Johann Gail -
Mark Burton -
Steve Ratcliffe -
Thilo Hannemann -
Valentijn Sessink