[MUD-Dev] Re: Quadtrees?

[Ling]

Not quite sure why I'm replying to this but anyway...

On Sun, 23 May 1999, Greg Munt wrote:
> >From the archives, dated 27 Feb 1997... (Whats up with WebGlimpse, btw?)
> 
> > [JCL]
> >
> > Unfortunately I have to go confront the IRS, so I'll have to keep this
> > quick.  I think Quadtrees are a *very* bad way to approach spaces in MUDs
> > as they don't lend themselves to the type of spatial processing that I
> > think MUDs require.  My own temptation would be to go for something close
> > to an R*-Tree approach (see below).
> 
> 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. When you get down to it, they both
> model the world, both starting from a general, 'big-picture', with child
> nodes describing smaller and smaller areas, in more and more detail. Would I
> be right in thinking that Q-Trees model only 1 aspect of the world, whereas
> R-Trees (anyone know what the 'R' means, btw?) can model the world in its
> entirety - and that this is why you don't like them? I think that you allude
> to this, later on.. (Marked [1])

R-trees utilises memory more efficiently.  A quadtree would divide in
itself in a systematic manner in the form of recursive squares of precise
dimensions.  R-trees, on the other hand, would look like a bunch of
bounding rectangles those dimensions are determined by the location of the
objects. 

The crunch with r-trees is splitting and merging nodes when they exceed
the minimum or maximum number of objects.  See Guttman's report for three
such techniques. 

Btw, "R" stands for range.

> I just don't get how R-Trees can model the third dimension. Re: node types
> discussed above, do you have a special node type for the z-axis?

I presume you can imagine a one dimensional r-tree which has a bounding
line.  Two-dimensional uses a bounding rectangle and three dimensions uses
a bounding oblong (a better description than rectangle).

Would it surprise you then that r-trees are used to store data in 20+
dimensions?  It is just a matter of adding another axis to each tuple and
therefore more constraints to the search.

Think about it.  With one dimension, you just bound along the x-axis.
With two dimensions, you bound along both x and y.  With three, you bound
along x, y and z.

To be pedantic, what you refer to as quadtrees are actually octrees if you
are thinking in cubes, not squares.  In a similar manner, you should think
of r-trees are storing bounding oblongs, not rectangles.

The disadvantage of r-trees is that they are computationally more
intensive to construct.

You may like to visit:

<URL:http://www.slip.net/~danielgr/sources/sources.htm>

  |    Ling Lo
_O_O_  kllo at iee.org



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