这些四叉树库有好用的吗？
看起来我有一个项目需要用到四叉树（quad-trees），但我之前从来没有接触过这个东西。根据我看到的资料，四叉树应该能比直接暴力解决问题的方式更有效率。请问这些Python模块有哪个比较好用吗？
- Quadtree 0.1.2 <= 不行：在Python 3.1中无法运行
- QuadTree <= 可以：在处理矩形时很简单
- quadtree.py <= 不行：不支持需要的操作
编辑 1：有没有人知道比pygame wiki上提供的实现更好的方法？
编辑 2：这里有一些其他人可能会觉得有用的关于Python路径寻找技术的资源。
4 个回答
有时候，在Python中实现像树这样的数据结构并不是那么明显。
比如说，
D
/ \
B F
/ \ / \
A C E G
这是一个简单的二叉树结构。在Python中，你可以这样表示它：
[D,B,F] 是一个节点，包含左子树和右子树。要表示整个树，你可以这样写：
[D,[[B,A,C],[F,E,G]]]
这其实是一个嵌套列表的简单列表，其中任何节点都可以是像D或C这样的值，任何节点也可以是一个子树，这个子树又是一个嵌套列表。你也可以用字典的字典来做类似的事情。这些实现方式虽然有点简单粗暴，可能在作业中不太符合老师的要求（老师可能希望你用一个节点类，并且有指向其他节点的指针），但在实际应用中，通常先用Python的列表或字典的优化实现会更好。如果结果在某种程度上不够理想，再改成更像C或Java那样的写法。
当然，除了这些，你还需要实现各种算法来操作你的树，因为四叉树不仅仅是一些数据；它是一套关于如何插入和删除节点的规则。如果这不是一个课程作业的问题，那么 Quadtree 0.1.2 可能是个不错的选择。
另一个值得关注的库是 PyQuadTree，这是一个纯Python编写的四叉树索引，适用于Python 3.x。你只需要提供一个物品的边界框，格式是一个包含四个数值的序列，就可以添加这个物品。这使得它可以用于多种用途，甚至可以处理负坐标系统。
虽然我是这个库的作者，但其实我只是把别人写的四叉树结构和代码进行了改进，让它更容易使用，增加了对矩形四叉树的支持，并且添加了文档。下面是一个简单的使用示例：
#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])
在这个评论中，joferkington提到了当前的问题，并说：
不管怎样，
scipy.spatial.KDTree（还有另一个叫做scipy.spatial.cKDTree，它是用C语言写的，主要是为了提高性能）比列出的其他选项要强大得多。