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

[Nigel Magnay]

I still don't understand why dividing the world into simple quadtiles has
any problems at all.

With a simple QT, I can represent, in, say, 64-bit integer form, the entire
planet down to roughly a square centimetre, which is, to be frank, a totally
unneccessary degree of accuracy, so the bottom few bits are somewhat
irrelevant.

The top-level tiles at, say, 32-bits gives about 610sqm in size. The edges
are easily definable in floating point values for doing 'is this value in
this area' conversions.

Having pre-parsed the entire OSM dataset (~15 million nodes) with and
without appending a calculated quadtile address (the earlier function) makes
a difference of about 10 seconds. For the entire dataset. Performance is a
total non-issue here, particularly compared with the gains to be had in the
actual querying of the data (we could replace many of the horrendous 'select
from blah where ID in (very_huge_list_of_numbers)).

The only thing I can see is that, at higher zoom levels, the edges don't
'line up' with degrees of longitude. But I can't help thinking "so what"? I
can't see what I'm loosing here. And if it's really that big a deal, then
why not scale the size of the tilemap to be bigger than the size of the
world? I.E - instead of having longitude values of +/- 180, have +/-200, and
just never have any data in the 180-200 range ? I don't like the idea of
'invalid' ranges, and I'm particularly worried by "some tile will disappear
along a fold in each quadrant" - I definitely don't want overlapping
tiles...



On 18/09/06, Nick Hill <nick at nickhill.co.uk> wrote:
>
> 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.
>
>
>
>
> _______________________________________________
> dev mailing list
> dev at openstreetmap.org
> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20060918/12e6e0cc/attachment.html>