[mkgmap-dev] Rounding bug in splitter?

Mon Aug 10 22:37:44 BST 2009

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