q-tree stuff

[Carter T Shock]

> Thanks Todd! The picture came out fine on my Amiga, so it must have
> worked on PC's, right? :-)

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 :)
> 
> To summarize my understanding here (you never know, I could have missed
> it altogether!), objects are stored in B-trees, in which the index is
[snip]
Yeah, that's pretty much the gist of it, but recall that that is a very
limited implementation. Without getting too gory, another variant is to
implement a B+-Tree and store codes for the morton blocks in internal nodes
and codes for point data in the leaves. Note that the morton block stuff
applies to all flavors of quadtrees (for linearizing them.. getting rid o'
the pointers). Use of morton codes to index the data itself is limited
usually to point data. You can choose a centroid for objects in higher
dimensions but it never works out that well in real life.

> If your "grids" get *very* big, so that having an array for them is not
> practical, then you do as Todd said - just have quad-trees representing
> the various properties that are needed to describe the location (terrain
> type, monster sets, weather, temperature, etc.)

Well, not really. The grid can be any size, the question is what is the
minimum feature size in the grid. Here we're talking region qtrees where
the blocks themselves become what we are interested in (you subdivide until
you have a whole block that is or is not "forest" or whatever). If you are
indexing Wyoming, things work extremely well because it's big and
rectangular. Trying to do something like fjords is messy as hell. lotsa
subdivision. The point is that I agree wholeheartedly. qtrees are not the
whole answer. Hybrid structures (a qtree of r-trees, an r-tree of qtrees,
k-d trees, various other esoterica) are usually the best solution. For
discrete data (i.e. not arbitrary region, but objects)   there are some
nice variants (check out "PMR Quadtrees"), but in general, qtrees tend to
do better with either sparse data sets or dense data sets with fairly
regular distribution. cities and fields in the same structure tend to do
better with r-trees, or r-tree-like structures. However, in light of your
wish to have a space that doesn't necessarily obey all of the rules of
physics....

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 :)
	-Todd (who is obviously in need of some sleep)