[DGD] Using r-trees to subdivide a world

[Jared Maddox]

> Date: Mon, 30 Jul 2012 04:55:04 -0700
> From: Shentino <shentino at gmail.com>
> To: All about DGD and Hydra <dgd at dworkin.nl>
> Subject: Re: [DGD] Using r-trees to subdivide a world
> Message-ID:
> 	<CAGDaZ_pN6sg1DfdOiqO_a-ZS1VCQNJ6j2y+T5OVH6zA21cBU9A at mail.gmail.com>
> Content-Type: text/plain; charset=UTF-8
>
> Anyway, what I needed advice with was a good r-tree type setup that
> generally avoids linear time operations for inventory management,
> allows me to locate an object by its XYZ coordinates, and can handle
> objects scooting around pretty much arbitrarily in 3 dimensions.
>
> I've looked at the r-tree article on wikipedia, and so far r*-tree
> looks good, but I have zero practical experience with r-trees in
> general.
>
> Most of the stuff I've found on r-tree setups assumes that the points
> aren't moving.
>

For moving points, I think I would just run a validity test (if the
point's new position is still inside it's container, it passes), and
on failure remove the point, and reinsert where appropriate.

But I also think I'd use a kd-tree, or maybe a splay-tree equivalent
inspired by a kd-tree (probably I'd use a separate tree for each axis,
instead of just one tree, since you could trivially implement this
with any binary tree implementation), so my advice may be off the
mark.

Why are you wanting to use r-trees specifically? Is it in some way
important that the sub-divided spaces correspond to explicit rooms?