# DESIGN: R-Trees (fwd)

Greg Munt greg at uni-corn.demon.co.uk
Sun Aug 24 22:48:56 New Zealand Standard Time 1997

```I should have known better, than to post this to rgma. I guess I won't
try too hard at being constructive there, anymore.

Sigh.

---------- Forwarded message ----------
Date: Tue, 19 Aug 1997 19:48:31 +0100
From: Greg Munt <greg at uni-corn.demon.co.uk>
Subject: DESIGN: R-Trees

The R-Tree is a model for representing spatial data. I'm considering an
R-Tree as the basis for some kind of co-ordinate system.

My understanding of the R-Tree model:

A tuple represents spatial data.

Each tuple has a unique identifier, the tuple-identifier.

Leaf nodes of the R-Tree have index records to reference the spatial data.

An index record: (I, tuple-identifier), where I is an n-dimensional
rectangle.

Non-leaf nodes: (I, childnode-pointer)

Each 'I' contains the areas contained by the rectangles referenced by
all of the child, grandchild, great-grandchild (etc) nodes.

Questions:

Is my understanding complete? Or am I missing vital details?

Could the tuple's data be effectively represented by a simple
three-dimensional matrix?

Any effective memory-saving methods that can be used with this model?

Are 'empty' nodes (Node H represents a large, featureless desert, so
no further detail (read: child nodes) are required?) simply deleted, or
is there some better way of dealing with them?

Efficient ways of determining an X*Y area around a certain point?
(Example: someone shouts a message, need to determine which parts of the
world that the shout can be heard from.) What about if the shout is
emitted from an index record 'border'? How easy is it to calculate the
X*Y area, if it falls over more than one leaf node?

Any other models that may be useful, that you have references for?

Is the size of the world limited by an early design decision? Or can
the size of the R-Tree 'grow'?

-------------------------------------------------------------------------------
"I want to be imp on a MU*!!! Where do I get the code for CircleMUD???"
"I have great ideas for a new mud, but if I use stock code I'll be flamed."
These are the two extremes. Can the pro-scratchers go too far?

```