在距离另一个点一定距离的 2D 网格上找到所有点的算法 [英] Algorithm to find all points on a 2D grid some distance away from another point

问题描述

我在 2D 网格 (x, y) 上有一个点，我需要找到距离该点 n 距离的所有点.我测量距离的方法是使用两点之间的距离公式.有人知道怎么做吗?

I have some point on a 2D grid (x, y) and I need to find all points that are n distance away from that point. The way I'm measuring distance is by using the distance formula between the two points. Anyone know how to do this?

仅供参考，我想要做的是编写一些 AI 路径查找，以便在使用基于网格的位置的系统中与目标保持一定距离.目前我正在使用 A* 路径查找，但我不确定这是否重要或有什么不同，因为我对这些东西有点陌生.

Just for reference, what I'm trying to do is to write some AI path finding that will maintain some distance away from a target in a system that uses grid based locations. Currently I'm using A* path finding, but I'm not sure if that matters or makes a difference since I'm kind of new to this stuff.

推荐答案

我会这样做:

1. 首先过滤掉所有在 x 或 y 上比 D 更远的点.这些肯定在半径 D 的圆之外.这是一个简单得多的计算，它可以很快消除很多工作.这是一个外部边界框优化.

1. First filter out all points that are further than D on either x or y. These are certainly outside the circle of radius D. This is a much simpler computation, and it can quickly eliminate a lot of work. This is a outer bounding-box optimization.

您还可以使用内部边界框优化.如果点在 x 或 y 上比 D * sqrt(2)/2 更近，那么它们肯定在半径 D 的圆内.这也比计算距离公式便宜.

You can also use an inner bounding-box optimization. If the points are closer than D * sqrt(2)/2 on either x or y, then they're certainly within the circle of radius D. This is also cheaper than calculating the distance formula.

然后你有较少数量的候选点可能在半径 D 的圆内.对于这些，使用距离公式.请记住，如果 D = sqrt(Δx²+Δy²)，则 D² = Δx²+Δy².
所以你可以跳过计算平方根的成本.

Then you have a smaller number of candidate points that may be within the circle of radius D. For these, use the distance formula. Remember that if D = sqrt(Δx²+Δy²), then D² = Δx²+Δy².
So you can skip the cost of calculating square root.

<小时>

因此在伪代码中，您可以执行以下操作:

---

So in pseudocode, you could do the following:

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

这篇关于在距离另一个点一定距离的 2D 网格上找到所有点的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！