18

我的某个项目似乎需要使用四叉树，这是我以前从未使用过的。从我所读到的内容来看，它们应该允许显着的性能增强，而不是对问题的蛮力尝试。这些python模块中的任何一个都好吗？

编辑 1：有谁知道比 pygame wiki 中提供的更好的实现？

编辑 2：这里有一些其他人可能会发现对 Python 中的寻路技术有用的资源。

4

4 回答 4

17

在此评论中，joferkington提到了当前的问题并说：

就其价值而言，scipy.spatial.KDTree（和/或 scipy.spatial.cKDTree，出于性能原因用 C 语言编写）是比列出的选项更可靠的选择。

于 2012-11-13T14:08:25.213 回答
6

另一个要检查的库是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])
于 2014-05-25T20:37:55.340 回答
1

有时，如何在 Python 中实现像树这样的数据结构并不明显。

例如，

      D 
    /   \
   B     F
  / \   / \
 A   C E   G

是一个简单的二叉树结构。在 Python 中，您可以这样表示它：

[D,B,F]是具有左右子树的节点。要表示完整的树，您将拥有：

[D,[[B,A,C],[F,E,G]]]

这是一个简单的嵌套列表列表，其中任何节点都可以是 D 或 C 之类的值，并且任何节点都可以是子树，递归地是嵌套列表的列表。你可以用字典做类似的事情。这些类型的实现有点快速和肮脏，并且在教师期望具有指向其他节点的指针的 N​​ode 类的作业中可能无法接受，但在现实世界中，通常最好使用 Python 列表/字典的优化实现第一的。只有当结果在某些方面不合适时，才将其重写为更像用 C 或 Java 编写的那样。

当然，除此之外，您还需要实现各种算法来操作您的树，因为四叉树不仅仅是一些数据。它是关于如何插入和删除节点的一​​组规则。如果这不是课程作业问题，那么Quadtree 0.1.2可能是一个好主意。

于 2010-02-19T20:54:44.443 回答
1

搜索四叉树时，python 包索引会生成 2 个其他库：http ://pypi.python.org/pypi?%3Aaction=search&term=quadtree&submit=search

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

于 2010-03-19T09:18:53.000 回答