1

我确信有一种干净的方法可以做到这一点，但我可能没有使用正确的关键字来查找它。

所以假设我有一个网格。从网格上的一个位置开始，返回给定距离内的所有网格坐标。所以我称之为：

getCoordinates( currentPosition, distance )

对于每个坐标，从初始位置开始，添加所有基本方向，然后在这些方向周围添加空格，依此类推，直到达到距离。我想在网格上这看起来像一颗钻石。该函数将返回该坐标数组。有人可以指出一个可以有效地做到这一点的例程（我在 AS3 工作，因为它的价值）？

在所需的输出中，迭代 1 将是：

.x.
xxx
.x.

迭代 2 将是：

..x..
.xxx.
xxxxx
.xxx.
..x..

迭代 3：

...x...
..xxx..
.xxxxx.
xxxxxxx
.xxxxx.
..xxx..
...x...

等等...

4

6 回答 6

7

编辑：更新了算法以反映 OP 想要什么。

迭代 1：

.x.
xxx
.x.

迭代 2：

..x..
.xxx.
xxxxx
.xxx.
..x..

... 迭代 4：

....x....
...xxx...
..xxxxx..
.xxxxxxx.
xxxxxxxxx
.xxxxxxx.
..xxxxx..
...xxx...
....x....

显然，您无需迭代即可确定坐标。

如果起点是(X, Y)，迭代次数是n

for(int i = x - n; i <= x + n; i++)
{
    for(int j = y - n; j <= y + n; j++)
    {
        int dx = abs(i - x);
        int dy = abs(j - y);
        if(dx + dy <= n) //Produces a diamond, n+1 would produce a diamond with cut corners
        {
            //The point at (i, j) is within the marked area.
        }
    }
}
于 2010-03-12T21:29:41.417 回答
2

这取决于您使用哪种数据结构来表示您的网格，但通常广度优先搜索应该为您解决这个问题。

于 2010-03-12T21:25:03.080 回答
0

Two possibilities, depending on what kins of distance you want and how much programming you are willing to do:

(1) Dijkstra's algorithm. If you imagine that each two neighboring points on you grid are connected (only vertical and horizontal connections, so each point has 4 neighbors), you'll get your diamond. You don't have to implement any data structure for the graph -- you only need to generate lists of neighbors for current vertex, as you go.

(2) Fast marching. This'll give you true Euclidean distance within the numerical error, so you'll get an approximate circle, not a diamond.

于 2010-03-12T21:41:58.630 回答
0

BFS + FIFO 队列：

P = U = 0;
Q[P] = currentPosition;
D[ Q[P] ] = 0; D[~all the rest~] = infinity (or really any flag, such as -1)

while ( P <= U )
{
  current = Q[P];
  ++P;

  for ( each neighbor N = (X', Y') of (current.X, current.Y) )
    if ( D[N] == inf && D[current] + 1 <= distance )
    {
      D[N] = D[current] + 1;

      ++U;
      Q[U] = N;
    }    
}
于 2010-03-12T21:36:40.590 回答
0

对于迭代 N，您希望所有点 P' 使得从 P 到 P' <= N 的距离，其中距离为 |X' - X| + |Y' - Y|。

for (int i = -N; i <= N; i++)
   for (int j = abs(i) - N; j <= N - abs(i); j++)
   {
      results.Add(new Point(X+i, Y+j));
   }
}

return results;
于 2010-03-12T22:07:30.007 回答
0

我意识到这个问题已有 9 年历史，但实际上从中心（在菱形中）径向迭代的算法看起来像：

for (int mag = 0; mag <= range; ++mag)
    for (int xm = 0; xm <= mag; ++xm)
    {
        int ym = mag - xm;
        int xms = (xm == 0) ? -1 : 1;
        int yms = (ym == 0) ? -1 : 1;
        for (int xs = -1; xs <= xms; xs += 2)
            for (int ys = -1; ys <= yms; ys += 2)
            {
                int x = x_centre + xm * xs;
                int y = y_centre + ym * ys;
                // Do whatever with x, y here
            }
    }
于 2019-05-08T20:41:30.627 回答