Are any of these quad-tree libraries any good?

Question

It appears that a certain project of mine will require the use of quad-trees, something that I have never worked with before. From what I have read they should allow substantial performance enhancements than a brute-force attempt at the problem would yield. Are any of these python modules any good?

• Quadtree 0.1.2 <= No: unable to execute in Python 3.1
• QuadTree <= Yes: simple while working with rectangles
• quadtree.py <= No: no support for needed operations

EDIT 1: Does anyone know of a better implementation than the one presented in the pygame wiki?

EDIT 2: Here are a few resources that others may find useful for path-finding techniques in Python.

• Game Entity Navigation
• Catch the Cootie

Answer 1

Sometimes it is not obvious how to implement data structures like trees in Python.

For instance,

     d
  b     f
 a c   e g

is a simple binary tree structure. In Python you would represent it like so:

[d,b,f] is a node with a left and right subtree. To represent the full tree you would have:

[d,[b,a,c],[f,e,g]] 

Beyond that, of course you need to implement the various algorithms to manipulate your trees because a quadtree is more than just some data, it is a set of rules about how to insert and delete nodes. If this is not a coursework question, then http://pypi.python.org/pypi/Quadtree/0.1.2 would probably be a good idea.

Answer 2

The python package index produces 2 other libraries when searching for quadtree : http://pypi.python.org/pypi?%3Aaction=search&amp;term=quadtree&amp;submit=search

disclaimer : never used quadtrees or any of these libraries.