Re: R+ trees was RE: quadtrees was (Re: [pygame] PROPOSAL: Faster Collision Checking: Ordering Sprites ...)

[Magnus Lie Hetland <magnus@hetland.org>]

Boehnker, Karl Wilhelm <BoehnkerK@msx.umsl.edu>:
>
> There's a project on sourceforge dealing with R+ Trees, but most of
> the links are broken. http://rplustree.sourceforge.net and they
> haven't released any files.
> 
> Here's the original paper, converted to pdf:
> http://www.umsl.edu/~boehnkek/vldb87.pdf  if anyone is interested.
> It definitely sounds cool.

There are many spatial access methods out there, apart from quadtrees
or R+ trees (including hBpi-trees, kd-trees, hybrid trees, R*
trees...) Some of them (such as the hybrid tree) are geared towards
high dimensionality. For two dimensions these optimizations wouldn't
matter that much... The basic R tree structures (e.g. R+ and R*) are
quite easy to implement.

But... Moving objects would mean rebuilding the trees; and we'd have
to rebuild them quite often (i.e. at the frame rate). I believe
(without being an expart on spatial access methods) that much of the
functionality of these methods would be rather4 useless to us -- all
we need is a spatial join. (It may be that that necessitates the other
functionality... I'm not really sure ;)

Anyway; searching at researchindex.com for "spatial join" turns up a
lot of interesting stuff. One I've looked at before (and which I think
looks very promising) is this one:

  http://citeseer.nj.nec.com/lo96spatial.html

It's about "spatial hash-joins". I haven't looked into the details,
but the technique looks efficient, and rather easy to implement. I
hadn't thought about using it for collision detection before this
discussion surfaced, but it seems it may be usable.

Another thing: I'm not sure whether techniques have been developed,
but I'm confident they could be, for incremental updates to structures
for calculating spatial joins. We have a strong use-case -- if someone
can think of a great idea, it would probably be quite easy to get it
published :) (By incremental I mean a technique for updating the
structure that requires less work than rebuilding it from scratch.)

Just a little braindump... ;)

- M

-- 
Magnus Lie Hetland               "Nothing shocks me. I'm a scientist." 
http://hetland.org                                   -- Indiana Jones
____________________________________
pygame mailing list
pygame-users@seul.org
http://pygame.seul.org