在给定半径范围内确定点的算法

Question

我不确定哪个数学概念可以支持我的问题。^^

假设我们有一个参考点PointA。问题是查找在给定半径内（使用坐标）的PointA周围的点。我的方法是计算每个点的距离（勾股定理），然后与给定半径进行比较。我确信这将在复杂性方面很差。

你有什么算法建议吗？ 非常感谢提供一个示例代码来解释。谢谢。

- jeff

---

你想要一个函数，它可以返回每个整数坐标对，这些坐标对距离给定的坐标对小于某个特定的距离吗？或者你有一组漂浮的物体，你想知道哪些物体在半径内？ - Scott Stafford

你可能想看一下这个SO的答案：https://dev59.com/NnM_5IYBdhLWcg3wlEJH - Scott Stafford

Answer 1

我会从围绕圆形创建一个框开始，然后先测试是否有任何东西落在框内。这样你就可以避免一直计算平方根和平方运算。选择框的一条边（比如左侧边），并计算其x值：

xMin = xOrigin - radius

然后满足以下任何条件的内容

xTest < xMin

可以忽略。对于所有四个边重复类似的操作。如果测试失败，停止在该点上工作。不要进行不必要的计算。

这告诉你一个点是接近但不一定在半径内。接下来计算：

abs(sqr(xOrigin - xTest) - sqr(yOrigin - yTest))

如果这个值小于半径的平方（你预先计算以避免使用平方根），那么你就有一个在半径内的点。

在首先预处理数据后，这是我能想到的最好方法。

- No one in particular

Answer 2

如果您的点没有被索引，那么这实际上是一种最优算法。有n个点，在没有任何其他索引的情况下，搜索所有点需要O(n)的时间。

一个微小的优化是跳过sqrt操作，并将坐标差的平方和与所需半径的平方进行比较。

如果您将对同一数据集进行多次查询，则可以使用各种索引方案来计算（O(n log n)），但可以使查找更快（其中m是找到的点数，为O(m + log n)）。 kd-trees可能是开始的地方。

- Anonymous

---

我想补充一下，如果您确信坐标都小于sqrt(DBL_MAX)，那么您才能跳过sqrt操作，而这通常是成立的。计算欧几里得距离的数值稳定方法只有在结果距离溢出时才会溢出。 - Victor Liu

@匿名用户 我知道这是一个旧问题..但是你如何对这些点建立索引？谢谢。 - MTA

Answer 3

最佳答案取决于维度数量，我假设您在二维或三维空间中工作。一个简单的方法是制作一个统一的单元格大小网格，称为“R”。然后将所有点固定到它们各自的单元格上。每个查询点仅与少量单元格相交，例如9个。然后只需要检查相交的单元格。更有效的方法是构建四叉树或KD树（还有很多其他选项，但对于2D，四叉树或KD树就足够了）。使用分层结构需要检查圆形-矩形相交，但这在KD-Tree最近邻算法中已经描述了（您只需要稍微修改即可）。如果您真的关心性能，可以构建多个网格（移位或旋转），并始终选择具有最接近点的单元格的网格，以便搜索仅限于最少数量的单元格。

- Libor

Answer 4

你唯一需要处理的复杂度就是距离的计算。只需筛选和简化这个计算，你就能达到最优。

如果你的“中心”是A(x,y)，那么对于任何点B(x1, y1)：

1/ 如果B在你所需的距离d内，则必须满足 x-x1 < d 和 y-y1 < d。首先检查这些条件以过滤任何“低垂果实”的排除。

2/ 不要计算距离，而是计算距离的平方，并将其与允许的最大距离的平方进行比较（你应该预先计算和引用它，而不是每次重新计算）。这意味着不必为每个点计算平方根。

这些都是相当小的优化，但假设点是未排序和随机的，这是你能得到的最好结果。

- Kirk Broadhurst