在距离另一个点一定距离的 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.
推荐答案
我会这样做:
首先过滤掉所有在 x 或 y 上比 D 更远的点.这些肯定在半径 D 的圆之外.这是一个简单得多的计算,它可以很快消除很多工作.这是一个外部边界框优化.
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(Δx2+Δy2),则 D2 = Δx2+Δy2.
所以你可以跳过计算平方根的成本.
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(Δx2+Δy2), then D2 = Δx2+Δy2.
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屋!