[OSM-dev] Proposal: Database accelerator and dirty tile marker based on simple algorithm.

[Nick Hill]

Nick Hill wrote:
> Hello Nigel
> You could, for example, use the two most significant bits to represent 
> each quadrant, then the two next most significant bits to select  the 
> next level quadrant and so on. With a 32 bit int, you can do this 16 
> times, dividing the planet into 4Bn portions, much like the tiles I 
> suggested.

> I haven't yet considered your quadtree proposal in enough depth to fully 
> compare the two approaches, but there are many similarities.

If we use a quadtree form, and make all represented values fit to base-2 
(to avoid ugly floats) we end up with

Bit number
1 Latitude sign  (MSB)
2 longitude sign
3 1073741824 units LAT
4 1073741824 units LON
5 536870912 LAT
6 536870912 LON
7 268435456
8 268435456
continuing in the binary series for as much precision as required.

To extract a latitude value, we'd  need to use bits 3,5,7,9,11,13,15 
etc. Shift the number then apply 2's compliment if bit 1 is set.

To extract longitude, bits 4,6,8,10,12,14 etc, shift, then apply 2's 
complement if bit 2 is set.

So the quadtree form is very similar to my suggestion. The difference is 
that bits 1-16 are lat for my form but for quadtree form, bits 
1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31 are lat.