Menu
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.
901
A current ubiquitous example of quadtrees can be seen in online map databases such as Google Maps (see Figure 3) and Microsoft's TerraServer ( Barclay et al., 2000). ...
Quadtrees are implemented in image compression, where each node consists of the average colour of each of its children. The deeper we visit in the tree, the more the detail of the image. Quadtrees are also implemented in searching for nodes in a two-dimensional area.
Quadtrees are used in image compression, where each node contains the average colour of each of its children. The deeper you traverse in the tree, the more the detail of the image. Quadtrees are also used in searching for nodes in a two-dimensional area.
The difference (algorithmically) is: in quadtrees, the data reaching a node is split into a fixed (2^d), equal size cells, whereas in kdtrees, the data is split into two regions based on some data analysis (e.g. the median of some coordinate).
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.
67
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
