在二维网格上找到距离另一点一定距离的所有点的算法

Question

我在一个二维网格(x,y)上有一些点，需要找到所有距离该点n个单位长度的点。我使用两点之间的距离公式来测量距离。请问有人知道如何做到这一点吗？

编辑: 仅供参考，我的目标是编写一些AI路径规划，以在基于网格位置的系统中保持一定距离离目标。目前我正在使用A*路径规划，但我不确定它是否重要或有所区别，因为我对这方面的知识还比较新。

- Justin G

---

你想要在那个范围内的点还是恰好相距那个距离的点？ - nycdan

理想的解决方案是所有距离恰好或在某个误差范围内的点。 - Justin G

Answer 1

这是我会做的事情：

1. 首先，过滤掉所有距离 x 或 y 轴上大于 D 的点。这些点一定在半径为 D 的圆外面。这个计算比较简单，可以快速地减少很多工作量。这是一个外部边界框优化。
2. 你也可以使用内部边界框优化。如果点在 x 或 y 轴上距离小于 D * sqrt(2)/2，则它们一定在半径为 D 的圆内。这个计算比计算距离公式更便宜。
3. 然后，你只需要考虑一小部分可能在半径为 D 的圆内的候选点。对于这些点，使用距离公式。记住，如果 D = sqrt(Δx²+Δy²)，那么 D² = Δx²+Δy²。
   所以你可以跳过计算平方根的开销。

---

因此，在伪代码中，你可以按照以下方式操作：

for each point
begin
    if test 1 indicates the point is outside the outer bounding box, 
    then skip this point

    if test 2 indicates the point is inside the inner bounding box, 
    then keep this point

    if test 3 indicates the point is inside the radius of the circle, 
    then keep this point
end

- Bill Karwin

---

您可以通过使用空间索引进一步优化算法。如果点的数量非常大，则这是正确的。如果点的数量不是很大，则构建空间索引的成本可能不值得。 - Alceu Costa

网格不是很大。我认为当前计划的世界大小只有大约256x256。 - Justin G

好的，首先我会过滤掉那些X和Y距离都在指定范围内的点，然后再使用内部边界框检查来过滤这些点？不确定如何使用第二部分。 - Justin G

谢谢，太好了 :) 我需要进行一些简单的测试以确保我得到想要的值，但我认为这可能正是我正在寻找的。 - Justin G

Answer 2

这个问题被称为范围查询。暴力解决方案就像你所描述的那样：计算所有点到参考点的距离，并返回那些距离小于所需范围值的点。

暴力算法的时间复杂度是O(N^2)。然而，有更有效的算法采用空间索引来减少算法复杂度和距离计算次数。例如，您可以使用R-Tree来索引您的点。

- Alceu Costa

Answer 3

这被称为最近邻搜索。更多信息请参见http://en.wikipedia.org/wiki/Nearest_neighbor_search。

有一些开源库可以实现这个功能。我使用过一个用C语言编写的库，推荐给大家：http://www.cs.umd.edu/~mount/ANN/。ANN代表近似最近邻，但是你可以关闭近似搜索，找到精确的最近邻。

- Tarandeep Gill

---

有趣的东西，但我认为它对于我目前所做的事情来说太过繁重了。不过我会记住它，以备将来需要。 - Justin G

Answer 4

这不会使用距离公式，但如果您正在寻找恰好相距n个距离的点，则可以使用sin/cos？

伪代码如下：

for degrees in range(360):
    x = cos(degrees) * n
    y = sin(degrees) * n
    print x, y

这将以360度间隔打印每个n点。

- Michael0x2a

Answer 5

Java 实现：

public static Set<Point> findNearbyPoints(Set<Point> pts, Point centerPt, double radius) {
    Set<Point> nearbyPtsSet = new HashSet<Point>();
    double innerBound = radius * (Math.sqrt(2.0) / 2.0);
    double radiusSq = radius * radius;
    for (Point pt : pts) {
        double xDist = Math.abs(centerPt.x - pt.x);
        double yDist = Math.abs(centerPt.y - pt.y);
        if (xDist > radius || yDist > radius)
            continue;
        if (xDist > innerBound || yDist > innerBound)
            continue;
        if (distSq(centerPt, pt) < radiusSq)
            nearbyPtsSet.add(pt);
    }
    return nearbyPtsSet;
}

- zc22