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

[Nick Hill]

Hello Nigel

Thank you very much for making the great, well-considered wiki page. It 
condenses and explains most of the salient points in the forgoing thread.

The only issue I have so far is that the quadtile structure elucidated 
symmetrically split the world recursively in quarters. If the split is 
symmetric, we end up with measures which form fractionals of an integer 
degree representation.

Let me explain; If we use two 32 bit ints to represent lat and lon, we 
could split the globe into 4.2949673Bn angular increments. Of course, 
this gives us best value in terms of precision for the bits available. 
However, this is at the expense of making conversion from degree to int 
and int to degree reliant on multiplying with a floating point 
irrational number coefficient. In the GPX trace table, I have foregone a 
small degree of the available precision (about 2mm for any location on 
the planet's surface) to use a decimal integer coefficient - 10000000 
instead of 11930464.711111111 recurring.

The 1E7 coefficient makes conversion to/from degrees totally intuitive, 
clean and fast. Hopefully, programmers to the API would be inclined to 
use integer increments of 100nD (nanodegree) as provided by the 1E7 
coefficient.

If we were to sub-divide the world in equal quarters from the start, we 
will end up with values which do not fit the 1E7 coefficient. I 
therefore suggest the quadtile function at bits 3 and 4 represents an 
asymmetric division. On the face of it this may seem messy, but it is 
really neat and clean, and makes degree based calculation easier and faster.

The first two bits represent sign for lat/lon. This naturally divides 
the world into quarters. But then, for the value to fit into the 1E7 
coefficient, we simply interleave the integer 1E-7 degree value. Bingo! 
That's it. It is very clean and easy to convert using degrees.

 From the freethepostcode database let's use a worked example:
51.523343 -0.135136 WC1E 6JL

Multiply with the 1E7 coefficient and make integer positive. Note the 
sign for later.

S=0       _LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL
515233430 00011110101101011101011010010110

s=1       _lllllllllllllllllllllllllllllll
1351360   00000000000101001001111011000000

Loose the MSB (which would otherwise be a sign bit) then interleave:

Capital = Lat Lower=Lon
s|S=sign bit
l|L=binary values from above

For an exact location, we get a 64 bit tile reference locating the 
object to within about 1cm
SsLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLl
0100001010101000100010110011001011100011011111001101001000101000

If we just take the first 32 bits, we get a 655m tile containing the object:
01000010101010001000101100110010

If we add the rest of the number into the object, we get the complete 
location:
11100011011111001101001000101000

Of course, everything works as per wiki page examples, but part of the 
number ranges will be invalid by using the 1E7 coefficient. In 
visualisation terms, some tile will disappear along a fold in each 
quadrant but for all workable mathematical or computing examples, this 
would be irrelevant and makes for a very obvious conversion function and 
consequently, potential widespread use of integer 100nD increments with 
associated computational savings.






Nigel Magnay wrote:
> Ok - I suspect I'm not explaining myself terribly well and the threading 
> gets a bit lost on emails. I have set up the following page on the Wiki:
> 
> http://wiki.openstreetmap.org/index.php/QuadTiles 
> <http://wiki.openstreetmap.org/index.php/QuadTiles>
> 
> I have tried to explain why I think tile addressing is essential, and 
> why it ought to be a quadtree implementation and not a simple 
> tile-addressing scheme, and some details of how it might work in practice.
> 
> Whether the address is packed into a 32 or 64-bit integer isn't really 
> that important in comparison. I have a suspicion that it will actually 
> be slower than just using fixed char arrays, but - I don't know mysql 
> that well, and it's totally amenable to experimentation and metric 
> gathering.
> 
> I'd like to see it in (an|the) API. I don't think it'd be that hard, but 
> it might make sense to resolve the current status of segments at the 
> same time.
>