在 python 四叉树中建立索引

Question

我有一组点及其坐标（纬度、经度），还有一个区域（一个框）。所有的点都在盒子里。现在我想考虑点的密度将点分布到小单元格（矩形）中。基本上，一个包含很多点的单元格应该被细分成较小的单元格，同时保持较大的单元格和少量的点。

我检查了this question，它和我几乎有同样的问题，但我找不到好的答案。我想我应该使用四叉树，但我发现的所有实现都没有提供。

例如，this库允许制作一棵与盒子相关联的树，然后我们可以按如下方式插入盒子：

spindex = Index(bbox=(0, 0, 100, 100))
for item in items:
    spindex.insert(item, item.bbox)

但是不允许插入点。此外，我需要获取单元格（或名称）的 ID，并检查某个点是否属于给定单元格。

Here 是我找到的另一个库。它确实允许插入点，但它没有给我单元格的 ID（或名称），所以我无法检查一个点是否属于某个单元格。请注意，树应该自动进行分解。

你能给我一个解决方案吗？谢谢。

Answer 1

最后，我最终使用了 Google 的 s2-geometry-library 和 Python 包装器。事实上，这个库创建的每个单元格都不是一个矩形（它是一个投影），但它满足了我的需要。该库已经将地球表面划分为不同级别的单元格（四叉树）。给定一个点 (lat,lng)，我可以轻松地在叶级别获得相应的单元格。从这些叶节点开始，我根据需要（单元格中的点数）向上合并单元格。 This教程详细解释了一切。

这是我的结果：

在 python 四叉树中建立索引

Indexing in python quadtree

python

python-2.7

python-3.x

quadtree