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

[Rene Dudfield <illumen@yahoo.com>]

The quadtree that I did kind of cheats for updates. 
It takes advantage of the fact that most of the
objects will not have moved very far, and therefore it
is likely that they will want to be in the same
quadtree node.  So it checks in its current quadtree
node first.




 --- Magnus Lie Hetland <magnus@hetland.org> wrote: >
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... ;)
> 

__________________________________________________
Do You Yahoo!?
Everything you'll ever need on one web page
from News and Sport to Email and Music Charts
http://uk.my.yahoo.com
____________________________________
pygame mailing list
pygame-users@seul.org
http://pygame.seul.org