February 1997
- Its nice to be back Nathan Yospe
- Its nice to be back coder@ibm.net
- Its nice to be back Nathan Yospe
- Testing coder@ibm.net
- Invitation to MUD Design Mailing List Chris Gray
- Invitation to MUD Design Mailing List coder@ibm.net
- Invitation to MUD Design Mailing List coder@ibm.net
- Invitation to MUD Design Mailing List coder@ibm.net
- Invitation to MUD Design Mailing List coder@ibm.net
- Wout's mailing list and old digests coder@ibm.net
- Wout's mailing list and old digests Wout Mertens
- Wout's mailing list and old digests coder@ibm.net
- Just a bit of musing Nathan Yospe
- Just a bit of musing Adam Wiggins
- Just a bit of musing coder@ibm.net
- Just a bit of musing Chris Gray
- Just a bit of musing Carter T Shock
- Just a bit of musing Chris Gray
- Just a bit of musing S001GMU@nova.wright.edu
- Just a bit of musing Dmitri Kondratiev
- Just a bit of musing Chris Gray
- Just a bit of musing Dmitri Kondratiev
- Just a bit of musing coder@ibm.net
- Just a bit of musing Jon A. Lambert
- Just a bit of musing coder@ibm.net
- Just a bit of musing coder@ibm.net
- Just a bit of musing clawrenc@cup.hp.com
- Just a bit of musing coder@ibm.net
- Just a bit of musing Carter T Shock
- Just a bit of musing Alex Oren
- Just a bit of musing Wout Mertens
- Just a bit of musing coder@ibm.net
- Just a bit of musing coder@ibm.net
- Just a bit of musing Wout Mertens
- Just a bit of musing Carter T Shock
- Just a bit of musing S001GMU@nova.wright.edu
- Just a bit of musing Chris Gray
- Just a bit of musing coder@ibm.net
- Just a bit of musing Nathan Yospe
- Just a bit of musing coder@ibm.net
- Just a bit of musing Jon A. Lambert
- Just a bit of musing Adam Wiggins
- Just a bit of musing coder@ibm.net
- Just a bit of musing GnomesHome@aol.com
- Just a bit of musing Carter T Shock
- Just a bit of musing Chris Gray
- Just a bit of musing coder@ibm.net
- Just a bit of musing Adam Wiggins
- Just a bit of musing Chris Gray
- Just a bit of musing Adam Wiggins
- Just a bit of musing claw@null.net
- Just a bit of musing Chris Gray
- Just a bit of musing claw@null.net
- Just a bit of musing Chris Gray
- Just a bit of musing Jon A. Lambert
- Just a bit of musing Chris Gray
- Just a bit of musing Carter T. Shock
- Just a bit of musing claw@null.net
- Just a bit of musing Wout Mertens
- Just a bit of musing coder@ibm.net
- Just a bit of musing Adam Wiggins
- Just a bit of musing coder@ibm.net
- Just a bit of musing Chris Gray
- Just a bit of musing Jon A. Lambert
- Just a bit of musing Chris Gray
- Just a bit of musing Jon A. Lambert
- Just a bit of musing Chris Gray
- Just a bit of musing Jon A. Lambert
- Just a bit of musing Travis Casey
- Just a bit of musing Jon A. Lambert
- Just a bit of musing clawrenc@cup.hp.com
- Just a bit of musing Nathan Yospe
- Just a bit of musing clawrenc@cup.hp.com
- Quadtrees? Wout Mertens
- Quadtrees? coder@ibm.net
- Quadtrees? Greg Munt
- Quadtrees? Ola Fosheim Grøstad
- 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@iee.org - Quadtrees? Miroslav Silovic
- Quadtrees? Chris Gray
- Quadtrees? Carter T Shock
- Quadtrees? S001GMU@nova.wright.edu
- Quadtrees? Carter T Shock
- Quadtrees? S001GMU@nova.wright.edu
- Quadtrees? coder@ibm.net
- Quadtrees? Chris Gray
- Quadtrees? Carter T Shock
- Quadtrees? coder@ibm.net
- Quadtrees? claw@kanga.nu