地理空间查询

Question

我正在开发一种算法和数据结构，以处理大量二维点的欧几里德距离查找。

我尝试在Google学术中研究过这个问题，但还没有找到有用的信息（可能是因为我不知道这个问题在文献中通常被称为什么）。

这是我考虑过的两种方法：

方法1：创建一个具有bucket的二维网格。将点插入到bucket中，并保留每个点桶的引用。 在使用距离D查找点P时，获取其桶B以及任何一个角落到B的距离小于D的所有桶。 最后，枚举所有这些桶中的点并计算到P的距离。

方法2：创建两个列表，每个列表按其中一个坐标（x，y）排序所有点。在使用距离D查找点P时，执行二分查找以找到每个列表中的两个点，以便找到点的切比雪夫距离到P < D的矩形区域。 最后，计算所有这些点到P的欧几里得距离。

我猜现代算法会远远优于这个，但对此的任何想法都被赞赏。

- loopbackbee

---

我不太有资格回答这个问题，但是这个链接可能会有所帮助——它解释了MongoDB的地理空间索引是如何实现的。http://www.kchodorow.com/blog/2011/06/08/mongo-in-flatland/ - Rich

你是在询问2D rendezvous还是2D range query？ - David Cary

@DavidCary 没有特别之处，不过它更类似于2D范围查询。该问题可以总结为“找到所有距离点P的欧几里得距离小于D的点”。 - loopbackbee

@Rich 很有趣。它看起来类似于我提到的方法1，即将点分桶在网格中。 - loopbackbee

我在这里遇到了类似的问题：https://dev59.com/-mnWa4cB1Zd3GeqP2aC0 - dranxo

Answer 1

一些有用的提示：

• 查看KDTree，这是一种k维树（在您的情况下是2d），是查找最近邻居的最佳方法之一。
• 也许您可以从空间数据库中受益，该数据库专门开发用于处理地理空间数据；
• 您可以使用上述任何内容来实现所需的距离函数。根据您的应用程序，您需要地图距离、大圆距离、恒定坡度距离、恒定轴承距离等。您应该知道您的距离函数。我通常使用大圆（haversine）距离来处理类似于谷歌地图和轨迹的距离。

如果您想要Python实现，可以使用scipy.spatial (文档)。从此模块中，函数query_ball_point((px, py), radius)似乎是您要寻找的内容。

希望这能帮到您！

- heltonbiker

---

特别是，四叉树（另一个称呼为2D KDTree）将是默认解决方案，特别是如果您在矩形坐标上使用欧几里得距离函数（即忽略地球表面的曲率）。 - Erik P.

@ErikP. 我认为四叉树是一个常规的细分方法（将正方形单元格一分为二，以获得半尺寸、更小的正方形单元格），而 KD 树并不一定将单元格分成相等大小的子单元格。相反，在 KD 树中，子单元格的尺寸将取决于单元格内点的分布。这是正确的吗？ - heltonbiker

我倾向于将细分的(不)规则性视为KDTrees(或四叉树)中的一个(重要!)实现选择，但我开始相信你是正确的，我的术语使用是非标准的。无论如何，在这种情况下，我认为原则上正常和不规则的细分都可以工作；这可能取决于点分布哪种方法最好。 - Erik P.

@ErikP。我曾经看到四叉树被用来对空间进行细分，这个空间有可能包含数据，例如Web地图上的地图空间。现在，如果你想对点云进行自身细分，KDtree方法使用不规则（优化）细分。当然，如果你需要在四叉树的空间内引用点的位置，那就是另一项任务了。所有这些都很神奇和有趣！ - heltonbiker

K-d树和四叉树看起来非常有趣，可能比网格方法更具优势，因为只在需要时进行细分。现在我只需要实现算法来查找圆中的所有点，但它似乎相当简单。谢谢，heltonbiker和Erik P！ - loopbackbee