Hi Steve/anyone, Can someone please clarify exactly how DivisionParser.round(Area) is supposed to behave? My understanding is that it is taking the area passed in and rounding the edges *outwards* to the nearest multiple of 0x0800. ie, the area should get a little bit bigger in each direction. If that is true, then I think there are a couple of bugs in the rounding up code, especially when dealing with negative values. Here's the output from some logging I put into DivisionParser.getTotalArea(): details=(41.23698949813843,-73.50664615631104) to (42.888779640197754,-69.93184089660645) minLat=1d52f7 maxLat=1e7faa minLon=ffcbba86 maxLon=ffce454c Rounded bounds=(41.220703125,-73.564453125) to (42.890625,-69.9609375) minLat=1d5000 maxLat=1e8000 minLon=ffcbb000 maxLon=ffce4000 As you can see, the min/max latitudes are both rounding 'outwards' and make the area bigger, as does the min longitude (though I think it should go to 0xffcbb800 not 0xffcbb000). The max longitude is rounding the other way and is making the area slightly smaller. This in turn leads to the following assertion failure (when processing massachusetts.osm with default settings and assertions enabled): Found val=1dc1ce42 lon=ffce4200 left=ffcbb000 right=ffce4000 Exception in thread "main" java.lang.AssertionError: -3259904 at uk.me.parabola.splitter.AreaSplitter.splitHoriz(AreaSplitter.java:101) at uk.me.parabola.splitter.AreaSplitter.split(AreaSplitter.java:74) at uk.me.parabola.splitter.Main.calculateAreas(Main.java:180) at uk.me.parabola.splitter.Main.split(Main.java:95) at uk.me.parabola.splitter.Main.main(Main.java:78) Another potential corner-case is when rounding the value 0 down. Because the check is for val > 0 rather than >= 0, it ends up being rounded down to 0xfffff800 rather than just being left as 0. Is that intended (not that I think that case matters so much)? Assuming my understanding above is correct, here's how I think the rounding methods should be implemented to give the correct rounding in all situations: private int roundDown(int val) { return val >> SHIFT << SHIFT; } private int roundUp(int val) { return (val + (1 << SHIFT) - 1) >> SHIFT << SHIFT; } I've tested this change successfully with several files including massachusetts.osm. What do you think, is it the right thing to be doing? Chris
Chris,
to behave? My understanding is that it is taking the area passed in and rounding the edges *outwards* to the nearest multiple of 0x0800.
Not _completely_ unrelated, I'm not sure if you know about this: http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2009q3/002789.html As far as I know, this has not been implemented in Splitter due to it's recent discovery. But maybe I'm mistaken. Best regards, Valentijn -- Durgerdamstraat 29, 1507 JL Zaandam; telefoon 075-7074579
Chris,
to behave? My understanding is that it is taking the area passed in and rounding the edges *outwards* to the nearest multiple of 0x0800.
Not _completely_ unrelated, I'm not sure if you know about this: http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2009q3/002789.html
As far as I know, this has not been implemented in Splitter due to it's recent discovery. But maybe I'm mistaken.
Interesting, thanks for point that out I hadn't seen that thread before now. I'll take some time later today to digest it all and see what can be done in the splitter to help solve the problem. Cheers, Chris
On Mon, Aug 10, 2009 at 09:37:44PM +0000, Chris Miller wrote:
Assuming my understanding above is correct, here's how I think the rounding methods should be implemented to give the correct rounding in all situations:
private int roundDown(int val) { return val >> SHIFT << SHIFT; }
I would write this as return val & ~(1 << SHIFT);
private int roundUp(int val) { return (val + (1 << SHIFT) - 1) >> SHIFT << SHIFT; }
And this one as return (val + ((1 << SHIFT) - 1))) & ~(1 << SHIFT); It's probably not a big deal, but if SHIFT is a compile-time constant and the compiler performs constant folding, the run-time code should be shorter and faster. Marko
private int roundDown(int val) { return val >> SHIFT << SHIFT; } I would write this as
return val & ~(1 << SHIFT);
That's not the same thing though. I assume you really mean: return val & ~((1 << SHIFT) - 1); And in fact that's what was there originally for positive numbers. Negative numbers were handled differently, for reasons I don't understand (hence why I'm asking on here). I think I still prefer val >> SHIFT << SHIFT, it's clearer what's happening (to me at least, I appreciate everything thinks about these things differently). It's also fewer clock cycles unless you're on a 286 or lower ;) Though the clock cycle argument isn't relevant here, the code is only called twice during the entire split!
private int roundUp(int val) { return (val + (1 << SHIFT) - 1) >> SHIFT << SHIFT; } And this one as
return (val + ((1 << SHIFT) - 1))) & ~(1 << SHIFT);
Again, that would need to be (val + ((1 << SHIFT) - 1))) & ~((1 << SHIFT) - 1);
It's probably not a big deal, but if SHIFT is a compile-time constant and the compiler performs constant folding, the run-time code should be shorter and faster.
Yep I'd seen that and had originally coded it that way. I've now actually moved the code to the Utils class and passed 'shift' in as a parameter for flexibility, and because in this case performance doesn't matter. Chris
On Tue, Aug 11, 2009 at 06:52:35AM +0000, Chris Miller wrote:
private int roundDown(int val) { return val >> SHIFT << SHIFT; } I would write this as
return val & ~(1 << SHIFT);
That's not the same thing though. I assume you really mean:
return val & ~((1 << SHIFT) - 1);
And in fact that's what was there originally for positive numbers. Negative numbers were handled differently, for reasons I don't understand (hence why I'm asking on here).
Oh, sorry, you are right, I forgot the -1.
I think I still prefer val >> SHIFT << SHIFT, it's clearer what's happening (to me at least, I appreciate everything thinks about these things differently). It's also fewer clock cycles unless you're on a 286 or lower ;) Though the clock cycle argument isn't relevant here, the code is only called twice during the entire split!
If that is the case, then it is better to aim for readability and maintainability. The bit-shifting expression should be easier to read than the monster bit-masking expression. And because you are shifting the same amount right and left, it won't matter whether you are using arithmetic or logical right shift (>>> or >> in Java). Sorry for the noise. Marko
If that is the case, then it is better to aim for readability and maintainability. The bit-shifting expression should be easier to read than the monster bit-masking expression. And because you are shifting the same amount right and left, it won't matter whether you are using arithmetic or logical right shift (>>> or >> in Java).
As you point out >>> or >> doesn't matter but thinking about it >>> probably helps the readability slightly so I'll change it to that.
Sorry for the noise.
Not at all, I'm grateful for you taking the time to have a look. The more eyes the better, as I've discovered plenty of times in the past it's all too easy for a subtle bug to slip through with this sort of thing. Chris
Hi On 10/08/09 22:37, Chris Miller wrote:
Hi Steve/anyone,
Can someone please clarify exactly how DivisionParser.round(Area) is supposed to behave? My understanding is that it is taking the area passed in and rounding
On past experience, it is pretty safe to assume that any rounding code written by me is incorrect until proven otherwise. ..Steve
Hi
On 10/08/09 22:37, Chris Miller wrote:
Hi Steve/anyone,
Can someone please clarify exactly how DivisionParser.round(Area) is supposed to behave? My understanding is that it is taking the area passed in and rounding
On past experience, it is pretty safe to assume that any rounding code written by me is incorrect until proven otherwise.
Haha OK, I'll bear that tip in mind ;) Thanks for clarifying. I haven't yet had time to read through and understand everything in the thread Valentijn pointed at (http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2009q3/002789.html) but my impression is that the conclusion was that the splitter should be rounding areas off to boundaries in multiples of 4096 rather than 2048? If that's so I'll have a look at fixing that tonight (hopefully it's as simple as setting SPLIT = 12 for AreaSplitter.limit(), DivisionParser.round()). Chris
Quoting Chris Miller <chris.miller@kbcfp.com>:
Hi
On 10/08/09 22:37, Chris Miller wrote:
Hi Steve/anyone,
Can someone please clarify exactly how DivisionParser.round(Area) is supposed to behave? My understanding is that it is taking the area passed in and rounding
On past experience, it is pretty safe to assume that any rounding code written by me is incorrect until proven otherwise.
Haha OK, I'll bear that tip in mind ;) Thanks for clarifying.
I haven't yet had time to read through and understand everything in the thread Valentijn pointed at (http://www.mkgmap.org.uk/pipermail/mkgmap-dev/2009q3/002789.html) but my impression is that the conclusion was that the splitter should be rounding areas off to boundaries in multiples of 4096 rather than 2048? If that's so I'll have a look at fixing that tonight (hopefully it's as simple as setting SPLIT = 12 for AreaSplitter.limit(), DivisionParser.round()). If you do that, does that mean that those of us who manually calculate our areas.list files as input to splitter will then need to ensure the bounding coordinates are divisible by 4096 rather than 2048? I guess it will only really matter when working on tiny test areas that could previously have been bounded in a 2048x2048 box and would now need to be bounded in a 4096x4096 box.
If you do that, does that mean that those of us who manually calculate our areas.list files as input to splitter will then need to ensure the bounding coordinates are divisible by 4096 rather than 2048?
No, the generation of areas.list is a completely separate step from the actual splitting that uses it. However...
I guess it will only really matter when working on tiny test areas that could previously have been bounded in a 2048x2048 box and would now need to be bounded in a 4096x4096 box.
...it seems you need to have the area borders aligned to 2048 map units(*) AND the area centre points must also be aligned to a 2048 map unit boundary. In practice this means that the area widths and heights must be multiples of 4096 even though the tile borders are only 2048 aligned. If you don't do this, you'll likely see some of the area-boundary problems that Valentijn descibed in the other thread. I have a fix for the splitter in the works, hopefully it will be checked in later tonight. If you're producing areas.list files by hand then I'd suggest you follow the same rules. (*) this number is dependent on the zoom level values in your style file. Chris
Chris Miller schreef:
but my impression is that the conclusion was that the splitter should be rounding areas off to boundaries in multiples of 4096 rather than 2048?
As far as I've seen - thanks to Steve Ratcliffe's findings - divisible by 2048 is enough, if you make sure that the difference is a multiple of 4096. (i.e. if your bounds are 0x123800 and 0x456800, that is OK; but 0x123800 and 0x456000 is not OK). Anyway, dividing by 4096 is a good method of achieving this. V.
Chris Miller schreef:
but my impression is that the conclusion was that the splitter should be rounding areas off to boundaries in multiples of 4096 rather than 2048?
As far as I've seen - thanks to Steve Ratcliffe's findings - divisible by 2048 is enough, if you make sure that the difference is a multiple of 4096. (i.e. if your bounds are 0x123800 and 0x456800, that is OK; but 0x123800 and 0x456000 is not OK).
Anyway, dividing by 4096 is a good method of achieving this.
V.
I see, the tile boundaries only need to be multiples of 2048, but the tile widths and heights must be multiples of 4096 - that makes sense to me now. I'll take a look and see what the best solution is to acheive this in the splitter. Chris
Hi Valentijn,
Chris Miller schreef:
but my impression is that the conclusion was that the splitter should be rounding areas off to boundaries in multiples of 4096 rather than 2048?
As far as I've seen - thanks to Steve Ratcliffe's findings - divisible by 2048 is enough, if you make sure that the difference is a multiple of 4096. (i.e. if your bounds are 0x123800 and 0x456800, that is OK; but 0x123800 and 0x456000 is not OK).
Anyway, dividing by 4096 is a good method of achieving this.
I've checked in what is hopefully a fix for this to the splitter. There's a new parameter called --resolution, which represents the lowest zoom level specified in your style file and dictates what boundaries to align the split tiles on. By default it's 13 which equates to tiles on boundaries of 2048 map units, and tiles with width/height in multiples of 4096 units. I've tested this with the netherlands.osm map and can't see any obvious problems (including around the tile borders and when routing across tiles), but as this is the first time I've used mkgmap to load osm files into MapSource I'm not 100% sure what I'm supposed to be looking for and your testing and comments would be appreciated. Have a play and let me know if you think it's an improvement. Cheers, Chris
Chris Miller wrote:
Hi Valentijn,
Chris Miller schreef:
but my impression is that the conclusion was that the splitter should be rounding areas off to boundaries in multiples of 4096 rather than 2048?
As far as I've seen - thanks to Steve Ratcliffe's findings - divisible by 2048 is enough, if you make sure that the difference is a multiple of 4096. (i.e. if your bounds are 0x123800 and 0x456800, that is OK; but 0x123800 and 0x456000 is not OK).
Anyway, dividing by 4096 is a good method of achieving this.
I've checked in what is hopefully a fix for this to the splitter. There's a new parameter called --resolution, which represents the lowest zoom level specified in your style file and dictates what boundaries to align the split tiles on. By default it's 13 which equates to tiles on boundaries of 2048 map units, and tiles with width/height in multiples of 4096 units.
the resolution option seems to be not working... I set resolution=15 but it defaults to 13. Actually if my lowest object is in resolution 16, meaning an empty level will be created at resolution 15, do I have to tell resolution=16 or resolution=15? - I assume 16, but to be on the safe side just went for 15..... Also since sometime the maxnodes seems to be disrepted, I noticed it this morning after updating from svn.... D:\Garmin\mkgmap>start /low /b /wait java -enableassertions -jar -Xmx1200M splitter.jar --mapid=63200000 --maxnodes=1000000 --resoultion=15 switzerland.osm /D:\Garmin\mkgmap>start /low /b /wait java -enableassertions -jar -Xmx1200M splitter.jar --mapid=63200000 /-/-maxnodes=1000000 --resoultion=15 switzerland.osm / /Time started: Thu Aug 13 01:03:10 CEST 2009 mapid = 63200000 maxnodes = 1000000 *resoultion = 15* Map is being split for *resolution 13:* - area boundaries are aligned to 0x800 map units - areas are multiples of 0x1000 map units wide and high Processing switzerland.osm 2.500.000 nodes processed... A total of 2595381 nodes were processed in 1 file Min node ID = 172204 Max node ID = 461905799 Time: Thu Aug 13 01:03:38 CEST 2009 Exact map coverage is (45.821378231048584,5.957551002502441) to (47.80904531478882,10.491621494293213) Rounded map coverage is (45.791015625,5.9326171875) to (47.8125,10.5029296875) Splitting nodes into areas containing a maximum of 1.600.000 nodes each... 2 areas generated: Area 63200000 contains *1.277.171 nodes *(45.791015625,5.9326171875) to (47.8125,8.1298828125) Area 63200001 contains *1.318.210 nodes* (45.791015625,8.1298828125) to (47.8125,10.5029296875) Writing out split osm files Thu Aug 13 01:03:38 CEST 2009 Processing 2 areas in a single pass Starting pass 1, processing 2 areas (63200000 to 63200001) 2.500.000 nodes processed... Writing ways Thu Aug 13 01:04:24 CEST 2009 Writing relations Thu Aug 13 01:04:44 CEST 2009 Wrote 2.595.381 nodes, 269.182 ways, 2.463 relations Time finished: Thu Aug 13 01:04:44 CEST 2009/
I've tested this with the netherlands.osm map and can't see any obvious problems (including around the tile borders and when routing across tiles), but as this is the first time I've used mkgmap to load osm files into MapSource I'm not 100% sure what I'm supposed to be looking for and your testing and comments would be appreciated.
Have a play and let me know if you think it's an improvement.
Cheers, Chris
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Felix Hartmann <extremecarver@googlemail.com> writes:
D:\Garmin\mkgmap>start /low /b /wait java -enableassertions -jar -Xmx1200M splitter.jar --mapid=63200000 --maxnodes=1000000 --resoultion=15 switzerland.osm
/D:\Garmin\mkgmap>start /low /b /wait java -enableassertions -jar -Xmx1200M splitter.jar --mapid=63200000 /-/-maxnodes=1000000 --resoultion=15 switzerland.osm /
You have spelled resolution incorrectly. Perhaps the splitter (and mkgmap) should error out when given an unknown option.
--=-=-=
Felix Hartmann <extremecarver@googlemail.com> writes:
D:\Garmin\mkgmap>start /low /b /wait java -enableassertions -jar -Xmx1200M splitter.jar --mapid=63200000 --maxnodes=1000000 --resoultion=15 switzerland.osm
/D:\Garmin\mkgmap>start /low /b /wait java -enableassertions -jar -Xmx1200M splitter.jar --mapid=63200000 /-/-maxnodes=1000000 --resoultion=15 switzerland.osm /
You have spelled resolution incorrectly. Perhaps the splitter (and mkgmap) should error out when given an unknown option.
--maxnodes too should in fact be --max-nodes. Improving the command-line handling has been on my todo list, though performance, key features and bugfixes have been higher priorities so far. Chris
participants (7)
-
charlie＠cferrero.net -
Chris Miller -
Felix Hartmann -
Greg Troxel -
Marko Mäkelä -
Steve Ratcliffe -
Valentijn Sessink