DESIGN: R-Trees (fwd)

[Greg Munt]

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>
Newgroups: rec.games.mud.admin
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?