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

问题描述

我在2D网格（x，y）上有一些点，我需要找到距离该点n距离的所有点。我测量距离的方式是使用两点之间的距离公式。任何人都知道如何做到这一点？编辑：只是作为参考，我想要做的是写一些AI路径发现，将保持一段距离远离目标在使用基于网格的位置的系统中。目前我正在使用A *路径查找，但我不确定这是否重要或有所作为，因为我对这种新东西很陌生。

解决方案

这是我会做的：

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

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



2. 然后您可以选择少于半数的候选点，它们可以在半径为D的圆内。对于这些，使用距离公式。请记住，如果D = sqrt（Δx2 +Δy2），则D 2 =Δx2 +Δy ² 。
   
   
   因此您可以跳过计算平方根的开销。

---

所以在伪代码中，您可以执行以下操作：

  for每个点
开始
，如果测试1指示该点在外边界框之外，则
然后跳过该点
 
如果测试2指示该点在内部如果测试3指出该点位于圆的半径内，则
然后保持此点
 
，
然后保持此点
结束
  

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?

Edit: 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.

解决方案

Here's what I would do:

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.

2. 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.

3. 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

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