[MUD-Dev] Re: Quadtrees?

[Ola Fosheim Grøstad <olag@ifi.uio.no>]

Greg Munt wrote:
> Why such a strong aversion to quad trees? Maybe this is illuminating my poor
> understanding of R-Trees, but the two don't seem to be as different as the
> degree of your aversion would attest.

I have no real experience with R-Trees, but in general there are two main
approaches to spatial searchstructures:

1. space subdivision
2. bounding hierarchies

A quad tree (and octree) is based on subdivision, and I believe R-tree
simply is a bounding hierarchy using rectangles? There are a sillion other
schemes and variations though, each with their own use.

As usual, discussing datastructures without knowing more about the design is
rather useless. Basically, this is one of the last things you want to decide
on.  There is no optimal search structure in general and certainly not in
higher dimensions. You need to consider whether your data is static or
dynamic, whether they are evenly distributed or clustered, density, what
kind of representation they have, what properties that characterize you data
(finite, infite, spherical, long, compact evenly sized etc), what kind of
queries, operations and sequences of operations you want to perform etc.

You might even combine different strategies, particularly static data may
benefit from a separate scheme. Maybe you even want to tailor your dataset
(world structure) to fit one particular scheme.

--
Ola Fosheim Groestad,Norway      http://www.stud.ifi.uio.no/~olag/


_______________________________________________
MUD-Dev maillist  -  MUD-Dev at kanga.nu
http://www.kanga.nu/lists/listinfo/mud-dev