[OSM-dev] Implementing a 2D-index - need feedback

[Marcus Wolschon]

2008/11/25 Marcus Wolschon <Marcus at wolschon.biz>:
>> I am starting to implement the 2D-indexing (lat+lon->{List of  NodeIDs})
>> for my binary file-format soon.
>>
>> http://wiki.openstreetmap.org/wiki/User:MarcusWolschon%5Cosmbin_draft#nodes.id2
>>
>> I want to use a 2-dimensional AVL-tree for it with 4 byte integers for the
>> coordinates (compatible with the osm-database-schemas) in a fixed-record-size
>> -format.
>>
>> Anyone have comments on my structure or ideas for a better datastructure to use
>> for such an index?

Hello,

>I'd probably go for a bucket quad tree with a not-too-small bucket size.
>However, as a general hint, you may want to take a look at some previous art regarding spatial data structures.
I don't particularly like the idea of a quadTree inserting
intermediate tree-nodes
at fixed intervalls in the key-space.
When I think of large rural areas next to large cities I don't think this kind
of tree will stay very balanced. This was fine for the index by ID, where our
keyspace is continous and 90% of it used.

> an AVL tree may or may not do the trick, depending on its implementation. Frankly,
> I don't currently see how it would work in 2D, but I haven't pondered it too deeply.
As for how a 2D-AVL-tree works, that's simple.
Every inner node has 2 values to compare against instead of one.
Thus you don't have LEFT and RIGHT but NORTHEAST, SOUTHEAST, NOTTHWEST
and SOUTHWEST
child-nodes. Of cause you also have 2 balance-factors of
{north,balanced,south}x{east,balanced,west} instead of  {-1, 0, 1}.

>You'll find some great demos here: http://donar.umiacs.umd.edu/quadtree/index.html Joerg Henne
The link you gave me was good but there was no explanation of the
data-structures presented. Either I don't understand the rectangles-section
or they don't do anything at all.

Marcus