No replies to this topic

[Nils Pipenbrinck]

While working on a rather complex clipping algorithm I read some papers and stumbled across a tree-structure that I've never seen mentioned before:

The R-Tree. (goggle is your friend)

I haven't reserached the tree in detail, but it looks like it is a nice alternative to solve the common "give me the rectanges that intersect this rectangle", and "in which rectangle is this point contained in".

The papers I've read are rather old and talk about disk-pages, offline storage and other 80th problems. Guess that has been a big deal back in the time when the R-tree was invented.

Anyways, that must not mean that the tree-structure itself is out of date..

Has anyone ever used one and has first hand experiences of the implementation complexity, performance and so on?

I'd be highly interested since from the first look at it looks like it's a great tool for spatial subdivision.