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

Nigel Magnay nigel.magnay at gmail.com
Sat Sep 16 16:46:42 BST 2006

```yes - use tiles, but I'd rather use quadtiles, as they have nicer properties
(particularly you can fetch the super-tile of 4 child tiles incredibly
easily. Calculating which tile a point is in is not very hard; I've got a
bit of java lying around, but it's easy enough to understand.

Incidentally, though I didn't mention it at the time, this scheme is
particularly good for databases that support data file partitioning.

Here's the post I sent a while ago:

> [sniiip]
> I'd be interested to hear from computer scientists about fancy algorithms
for
> spacially-sorting the data, doing indexes, etc. First person to mention
> Hilbert space gets a nerd of the month award.
>

Quadtrees. We need to be doing this in OSM in general, and it would
make things much simpler.

To illustrate - divide the world into 4 quadrants. Call the top-left
A, top-right B, bottom-left C, bottom-right D. Then for each quadrant,
do the same. thus the grid is now

AA AB BA BB
CA CB DA DB
CC CD DC DD

each time you repeat this process (and you can do this as much as you
like), you halve the area in each addressable tile. For around 13
characters, you get (IIRC) 100m of resolution if you started with the
entire globe (may be wrong, memory is hazy).

So, just thinking about nodes, we store along with each (long, lat)

select * from nodes where lat>? and lat<? and lon>? and lon<?

we just do (say)
select * from nodes where quadtree='AAABDBA'

rather neatly, if you wanted to zoom out to the next level of detail, you
can do

select  * from nodes where quadtree like 'AAABDB%'

Which will get any node in AAABDBA, AAABDBB, AAABDBC and AAABDBD. This
is a single index lookup, and is very fast.

This also solves another sticky problem. Consider segments (ways are
just the same on a larger scale). You have a segment going from AB to
BC. Using the current 'get nodes in area, get missing nodes in
segments' method, if you fetch the area AD, you'll miss the fact that
there is this segment going through it. By storing for each
way/segment the list of tiles it intersects, the segments query is
also simplified to 'select * from segments where quadtree like 'xyz%'.

This is particularly important for areas - for example, you could be
viewing a tile in the middle of a forest whose edge does not actually
intersect with your tile at all.

This makes the map query somewhat easy, just a sequence of
select * from nodes where quadtile like ?
select * from segments join segment_quadtile on
etc., etc.

changed. Map renderers can thus use this information to invalidate
their cache for just that tile, and re-render, without having to check
for changes each time. I could 'register' for information if anything