Python QuadTree索引返回节点

Question

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

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

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

Answer 1

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