当前位置：文江博客话题详情

这些四叉树库中的任何一个都好吗？

发布于 2024-08-22 01:21:01 字数 886 浏览 6 评论 0原文

看来我的某个项目需要使用四叉树，这是我以前从未使用过的。根据我所读到的内容，它们应该能够比暴力尝试解决问题所产生的性能显着提高。这些 python 模块有什么好处吗？

Quadtree 0.1.2 <= 否：无法在Python 3.1中执行
QuadTree <= 是：工作时简单带有矩形
quadtree.py <= 否：不支持对于所需的操作

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

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

烟花肆意 2024-08-29 01:21:01

在此评论< /a>, joferkington 指的是当前问题并表示：

无论它的价值如何，scipy.spatial.KDTree（和/或 scipy.spatial.cKDTree，出于性能原因用 C 编写）是比列出的选项更强大的选择。

回复收藏 0 原文

情魔剑神 2024-08-29 01:21:01

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

Another library to check out is PyQuadTree, a pure python quadtree index that also works on Python 3x. All you need to add an item is its bounding box as a 4-length sequence, so it could be used for a variety of purposes and even negative coordinate systems.

Although I am the author, I really just took someone else's quadtree structure/code and made it more user-friendly, added support for rectangle-quads, and added documentation. A simple example of how to use it:

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

回复收藏 0 原文

风月客 2024-08-29 01:21:01

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

例如，

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

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

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

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

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

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

Sometimes, it is not obvious how to implement data structures like trees in Python.

For instance,

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

is a simple binary tree structure. In Python, you would represent it like so:

[D,B,F] is a node with a left and right subtree. To represent the full tree you would have:

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

That is a simple list of nested lists where any node can be a value like D or C, and any node can be a subtree which is, recursively, a list of nested lists. You could do something similar with a dictionary of dictionaries. These types of implementations are a bit quick and dirty and might not be acceptable in an assignment where the instructor expects a Node class with pointers to other nodes, but in the real world it is generally better to use the optimized implementations of Python lists/dictionaries first. Only if the result is inadequate in some way, rewrite it to be more like you would write it in C or Java.

Beyond that of course you need to implement the various algorithms to manipulate your trees because a quadtree is more than just some data; it is a set of rules about how to insert and delete nodes. If this is not a coursework question, then Quadtree 0.1.2 would probably be a good idea.

回复收藏 0 原文