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

Nick Hill nick at nickhill.co.uk
Mon Sep 18 10:59:34 BST 2006


Nigel Magnay wrote:
> 
> I've become confused... - for longitude, the world is -180 to +180. 
> Dividing the tiles down by halves gives you 90, 45, 22.5, etc., etc - I 
> don't follow where this is irrational? 

I never said that function is irrational.

The function I am proposing is almost identical, except that in the 
interests of fitting the tile system neatly into an integer-degree based 
co-ordinate system, we correct the system to use the most significant 
bits of the 1E7 location system. The result is very similar.

The 1E7 system is my system which has been deployed in the GPS point 
database. It provides for easy conversion between integer and degree, 
with a good level of accuracy.

All objects in the database are likely to eventually be stored in the 
1E7 system as it provides 1cm accuracy with small data storage 
requirements, fast conversion to/from float degrees, and fast look-ups.

The 1E7 system is so-called because to convert from a float degree value 
to the 1E7 integer system, you multiply the float value by 1E7. To 
convert the other way, multiply by 1E-7 (or simply move the decimal point).

Using a corrected quadtile system with the 1E7 system is computationally 
trivial. The tile any object is in is derived from interleaving the most 
significant bits of its lat/lon.

The tiles within a degree or 1E7 bounding box are trivially easy to 
determine using code similar to that which I proposed earlier. By taking 
a 32 bit 1E7 quadtile reference, then adding another 32 bit word, we get 
the full location of an object to 1cm.







More information about the dev mailing list