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)).

<br><br>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...

<br><br><br><br><div><span class="gmail_quote">On 18/09/06, <b class="gmail_sendername">Nick Hill</b> <<a href="mailto:nick@nickhill.co.uk">nick@nickhill.co.uk</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

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?

<br><br>I never said that function is irrational.<br><br>The function I am proposing is almost identical, except that in the<br>interests of fitting the tile system neatly into an integer-degree based<br>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.

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

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).

<br><br>Using a corrected quadtile system with the 1E7 system is computationally<br>trivial. The tile any object is in is derived from interleaving the most<br>significant bits of its lat/lon.<br><br>The tiles within a degree or 1E7 bounding box are trivially easy to

<br>determine using code similar to that which I proposed earlier. By taking<br>a 32 bit 1E7 quadtile reference, then adding another 32 bit word, we get<br>the full location of an object to 1cm.<br><br><br><br><br>_______________________________________________

<br>dev mailing list<br><a href="mailto:dev@openstreetmap.org">dev@openstreetmap.org</a><br><a href="http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/dev">http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/dev

</a><br></blockquote></div><br>