[OSM-dev] Splitting the planet into thousands of pieces in one pass.

[andrzej zaborowski]

Hi Nic and Scott,

On 1 December 2010 14:27, Nic Roets <nroets at gmail.com> wrote:
> http://trac.openstreetmap.org/browser/applications/rendering/gosmore/bboxSplit.cpp?rev=24484

A further comment on splitting a big dataset into areas is that if the
areas are disjoint (like in the case of countries, provinces and other
administrative areas) or nearly disjoint (like in the case of their
bboxes) you can build a sort of look-up tree from the list of bboxes,
so that with n bboxes you only need a little more than log n "is this
node inside?" checks.  So for example if you're splitting the planet
into 20000 areas, you only need about 15 tests for every node by doing
a sort of bisection search.

I see that bboxSplit.cpp tests against every single bbox, I haven't
looked at Scott's mkgmap code.

Cheers