q-tree stuff

[coder at ibm.net]

On 02/03/97 at 11:34 PM, "Carter T Shock" <ctso at umiacs.umd.edu> said:

>Whew. Bit of honesty here.. I am completely new to PC's, windoze, MIME
>et. al. Got my first ever PC about a month ago. Eunuchs rules :) > 

I don't envy you.  The PC world is not a pretty one.  The more I dig away
from it, the better I end up liking it.

>One huge advantage of qtrees over rtrees is that a spatial join is very
>efficient. Qtrees are like binary trees where every node in the tree is
>itself a qtree; rtrees don't have this property (since they tend to be
>built like B-Trees). This means that you can take some chunk of one
>quadtree, offset it to the coordinates of another quadtree and then merge
>the two structures fairly easily and quickly. Generally with rtrees this
>forces a rebuild. One potential application is a hunk of the world that
>moves around, toting it's contents with it. Another interesting
>side-effect is the dimensional porthole bit... you can have several
>spaces indexed by different qtrees that may at one time or another share
>some nodes. Where and when they intersect defines the porthole :)

While I'm still working on the representational details, this would appear
to also be fairly easy (if not as trivial) to do with an R*-Tree given the
ability for a bounded reagion to redefine its coordinate system.  Once
that is done, the problem of translocating or even sharing the region then
just becomes a problem of moving or cross-linking the root node of the
bounded region.  Allowing redefinition of the coordinate system has other
advatnages, such as allowing TARDIS-like objects, geometric
inconsistancies, accurate representations of mobious strips (and even
klein bottles?), and heck, were you even so persuaded, multiple full
spherical planetary surfaces, worlds within worlds (ala Pelucidar), the
old crystal spheres concept etc

--
J C Lawrence                               Internet: claw at null.net
----------(*)                              Internet: coder at ibm.net
...Honourary Member of Clan McFud -- Teamer's Avenging Monolith...