这些四树图书馆中的任何一个都不错吗？

Question

似乎我的某个项目需要使用四叉树,这是我以前从未使用过的.从我所看到的,他们应该允许大量的性能增强,而不是蛮力尝试解决问题.这些python模块中的任何一个都不错吗？

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

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

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

• 游戏实体导航
• 抓住Cootie

Answer 1

在这篇评论中,joferkington提到了当前的问题并说:

只是为了它的价值,scipy.spatial.KDTree(和/或scipy.spatial.cKDTree,出于性能原因用C语言编写)是一个比列出的选项更强大的选择.

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