使用KD树（python）创建基于数据的地理网格

Question

在我的研究中，我需要用网格划分一个城市（如芝加哥或纽约）的地理区域。我想把它的经度和它的经度数据关联起来。在

最简单的方法是将空间划分为大小相同的正方形单元。然而，这将导致在人口稀少（农村地区）的小区和点数较多的小区（市中心）。为了获得更公平的表示以及点的数量和单元大小之间的关系，基于数据密度创建单元大小的自适应网格将是一个更好的选择。在

我遇到了this paper，它使用K-D树进行空间划分并从节点中检索单元。但是，我找不到任何implementation（在python中）可以做到这一点。现有的许多实现只索引树中的数据点来执行最近邻搜索，但它们没有提供代码来提取k-d树生成的多边形矩形。在

例如，给定以下图像：

我得到的网格将包含5个单元格（node1到node5），每个单元格都包含相关的数据点。在

有什么办法吗？在

有人知道什么实现吗？在

非常感谢， 大卫