这些四叉树库中有没有好的?

在 this comment , joferkington 引用当前问题并说:

不管它值多少钱, scipy.spatial.KDTree (和/或scipy.spatial.ckdtree,出于性能原因用C语言编写)是比所列选项更可靠的选择。

另一个要签出的库是 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])

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

免责声明:从不使用四叉树或任何这些库。

有时,如何在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 可能是个好主意。