Skip to main content
 首页 » 编程设计

Python QuadTree 索引返回节点

2025年05月04日10over140

我有一个包含点的城市边界框。我想根据点的重要性将这个边界框分成子框。例如,具有更多点的区域应该对应更多数量的子框。点数较少的区域应该响应宽度较大的较少框。

我知道一个好的数据结构是四叉树或者 KD 树。事实证明,这些库中的大多数只是返回最近的邻居(这是它们的主要用途)。我想要的不是最近的邻居,而是一个点的子框。 (让我们说叶ID)这可能吗?或四叉树数据结构是否正确使用? 换句话说,我需要四叉树只是为了将区域划分为子框而不是用作索引。

天真的解决方案是将边界框划分为相等的子框。

请您参考如下方法:

这本质上是一个R-Tree做。它基于边界矩形(框)生成或多或少平衡的树,但基于适合框内而不是框区域的几何对象的数量。另一方面,KD-Trees 递归地首先在 x 方向然后在 y 方向划分空间,这可以使搜索非常有效,但不能针对点密度较低或较高的区域进行调整。这里有一个 R-Trees 的 Python 实现,https://pypi.python.org/pypi/Rtree/ .我从未使用过它(它内置于我一直使用的 Postgres/Postgis 中),但我看起来它可能对您描述的内容有用。