Python QuadTree索引返回节点 [英] Python QuadTree index returning nodes

问题描述

我有一个包含点的城市的边界框.我想根据点的重要性将此边界框划分为子框.例如，具有更多点的区域应对应于更多数量的子框.点数较少的区域对宽度较大的框的响应应较少.

I have a bounding box of a city containing points. I would like to divide this bounding box into sub boxes according to the importance of the points. For example, regions with more points should correspond to higher number of sub-boxes. Regions with less points should respond to less boxes with larger width.

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

I understood that a good data structure for that is a quad tree or maybe a KD-Tree. It turns out that most of these libraries just return me the nearest neighbor (This is their main use). I would like to have not the nearest neighbor but the sub box of a point. (lets say leaf id) Is this possible? or event the Quadtree-Data structure the correct to use ? In other words I need the quad tree just to divide the region into sub boxes and not to be used as an index.

幼稚的解决方案是将边界框划分为相等的子框.

The naive solution is to just to divide the bounding box into equal sub boxes.

推荐答案

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

This is essentially what an R-Tree does. It produces a more or less balanced tree, based on bounding rectangles (boxes), but based on the number of geometric objects that fit inside the box, not on the boxes's area. KD-Trees, on the other hand, recursively divide a space first in the x and then in the y direction, which can make for very efficient searching, but can not be adjusted for areas with a lower or higher density of points. There is a Python implementation of R-Trees here, https://pypi.python.org/pypi/Rtree/. I have never used this (it is built into Postgres/Postgis which I use all the time), but I looks like it could be useful for what you describe.

这篇关于Python QuadTree索引返回节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！