Re: [pygame] quadtrees

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

On Fri, 3 Oct 2003 05:08 am, Gerrit Holl wrote:
> I am looking for resources on quadtrees. I am unable to find
> a gentle introduction on the WWW, and I do not understand how
> to implement them in Python. Are quadtrees useful for a game
> with a lot of useful objects? As I Understand It, the ordering
> depends on the place of objects. Does that mean I will have to
> change the ordering over and over again?
>
> Has anyone ever implemented quadtrees in Python?

Just a thought (relating to the recent discussion about NN-queries in
2d): By using a Voronoi tesselation and a point location algorithm you
can get a structure where you can add a point in O(log n) time and
search for the nearest neighbor of a query point also in O(log n)
time. (Similar stuff can be done with Delaunay triangulations, for
example by temporarily adding the query point to the triangulation.)

Even though quadtrees (and relatives) may be unbalanced, they are
simpler, so it may be just as easy to use them, I guess. If you move
your objects, the tree must be reconstructed, of course, but that goes
for any such structure. Adding and removing objects isn't really
expensive, though (O(log n) expected time, as with unbalanced binary
search trees, for example).

In case there are others here interested in general proximity search,
I found the mention of the use of Delaunay triangulations in the
following paper, which is very good, IMO:

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

(I haven't found any descriptions of the Delaunay NN-search algorithm
online, though, other than the approach of adding the query to the
triangulation.)

-- 
Magnus Lie Hetland                "In this house we obey the laws of
http://hetland.org                 thermodynamics!"    Homer Simpson