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

[Nigel Magnay]

[inline]

On 16/09/06, Nick Hill <nick at nickhill.co.uk> wrote:
>
>
>
> 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.


This is required though, otherwise fetching supertiles (e.g. 'D' from my
example) can't be done with a range lookup.

e.g: As quadtiles
AA AB BA BB
AC AD BC BD
CA CB DA DB
CC CD DC DD

== as bits

0000 0001 0100 0101
0010 0011 0110 0111
1000 1001 1100 1101
1010 1011 1110 1111

== as numbers

0 1 4 5
2 3 6 5
8 9 12 13
10 11 14 15

Fetch the bottom-right quadrant of the map is either ' like D%' or 'where
val >= 12 and <= 15).

This is very important if you ever want tiles that are > than the minimum
size. If you're doing,say, tiles that are composed of some size greater than
the maximum resolution. For example, you have a tile address

AAAB

and a 'tile invalidated' message arrives, for tile AAABABFB, you know,
trivially, that your tile is now invalid. The same can be done with pairs of
numbers, (e.g tile 9 invalidated, my tile is >=0,<=15) but it's a bit
uglier.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20060916/b9ff109d/attachment.html>