20

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?

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.

Noctis Skytower
  • 21,433
  • 16
  • 79
  • 117
  • 2
    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. – John Feminella Feb 19 '10 at 18:05

4 Answers4

18

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.

gerrit
  • 24,025
  • 17
  • 97
  • 170
Robert Pollak
  • 3,751
  • 4
  • 30
  • 54
  • 2
    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). – al45tair Mar 07 '13 at 13:25
  • 3
    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. – jwd Nov 03 '19 at 19:27
7

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])
Karim Bahgat
  • 2,781
  • 3
  • 21
  • 27
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]]]

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.

Noctis Skytower
  • 21,433
  • 16
  • 79
  • 117
Michael Dillon
  • 31,973
  • 6
  • 70
  • 106
  • 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. – Noctis Skytower Feb 19 '10 at 21:31
  • 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. – Michael Dillon Feb 22 '10 at 23:48
1

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.

gurney alex
  • 13,247
  • 4
  • 43
  • 57