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

Windtight

I think you skipped a step here: if you have "no previous experience with quad-trees and no idea how to use them", then how do you know a quadtree library is what you need? Even assuming you found a perfect match for your needs, wouldn't you have trouble using it correctly? IMO, you need study the problem a little bit more before you start implementing things. – Selig

Answer 1

In this comment, joferkington refers to the current question and says:

Just for whatever it's worth, scipy.spatial.KDTree (and/or scipy.spatial.cKDTree, which is written in C for performance reasons) is a far more robust choice than the options listed.

Prudery

To be fair, scipy.spatial.KDTree is only a better solution if installing scipy is an option. It might not be (scipy has some interesting dependencies). – Gunnery

Note that scipy's KDTree is oriented towards clustering use-cases and also has some not-obvious-to-non-scientist terminology. For instance, want to query the tree for all points in an AABB? Well then you need to use query_ball_point with p=1, of course (: But you still can't input your own box shape (it's always a "sphere"). Also doesn't support dynamic updates. It's good code, but may require more work to understand and get what you want out of it than some other solutions. – Vespers

Answer 2

Another library to check out is PyQuadTree, a pure python quadtree index that also works on Python 3x. All you need to add an item is its bounding box as a 4-length sequence, so it could be used for a variety of purposes and even negative coordinate systems.

Although I am the author, I really just took someone else's quadtree structure/code and made it more user-friendly, added support for rectangle-quads, and added documentation. A simple example of how to use it:

#SETUP
import pyqtree
spindex = pyqtree.Index(bbox=[0,0,1000,500])

#ADD SOME ITEMS
for item in items:
    spindex.insert(item=item, bbox=item.bbox)

#RETRIEVE ITEMS FROM A REGION
result = spindex.intersect(bbox=[233,121,356,242])

Broadleaf

Answer 3

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]]] 

That is a simple list of nested lists where any node can be a value like D or C, and any node can be a subtree which is, recursively, a list of nested lists. You could do something similar with a dictionary of dictionaries. These types of implementations are a bit quick and dirty and might not be acceptable in an assignment where the instructor expects a Node class with pointers to other nodes, but in the real world it is generally better to use the optimized implementations of Python lists/dictionaries first. Only if the result is inadequate in some way, rewrite it to be more like you would write it in C or Java.

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 Quadtree 0.1.2 would probably be a good idea.

Ampoule

Quadtree 0.1.2 will not work in Python 3.1 since there is no setuptools. The source needs to be compiled first to work on Windows. – Windtight

If you really need the performance, then you could compile the module for Python 3.1. If you can't do this yourself, then go onto comp.lang.python and ask if there is someone who can do it for you. – Ampoule

Answer 4

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

disclaimer : never used quadtrees or any of these libraries.

Angelangela

This appears to be the best answer. It does not help, but it is the best. – Windtight