这些四叉树库有什么好的吗？

Question

似乎我的某个项目需要使用四叉树，这是我以前从未使用过的。从我所读到的内容来看，它们应该允许大量的性能增强，而不是对问题的野蛮尝试所产生的效果。这些python模块有什么好的吗？

• Quadtree 0.1.2<；=否：无法在Python 3.1中执行
• QuadTree<；=是：使用矩形时很简单
• quadtree.py<；=否：不支持所需的操作

编辑1:是否有人知道比pygame wiki中提供的实现更好的实现？

编辑2:以下是一些其他人可能会发现对Python中的路径查找技术有用的资源。

• Game Entity Navigation
• Catch the Cootie

Answer 1

python包索引在搜索四叉树时生成另外两个库：http://pypi.python.org/pypi?%3Aaction=search&term=quadtree&submit=search

免责声明：从未使用过四叉树或任何这些库。

Answer 2

另一个要检查的库是PyQuadTree，这是一个纯python四叉树索引，也可以在python 3x上工作。您只需要添加一个项作为4长度序列的边界框，这样它就可以用于各种用途，甚至负坐标系。

虽然我是作者，但我实际上只是采用了其他人的四叉树结构/代码，使其更加用户友好，添加了对矩形四叉树的支持，并添加了文档。如何使用它的一个简单示例：

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

Answer 3

在this comment中，joferkington引用当前问题并说：

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.