Are any of these quad-tree libraries any good?

user_216356 0
Viewed 18014

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.

quadtree python performance
4 Answers

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.

user_1893610
user_2813680
Related