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

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

必要な距離の種類と実行するプログラミングの量に応じて、2つの可能性があります。

（1）ダイクストラのアルゴリズム。グリッド上の2つの隣接する各ポイントが接続されていると想像すると（垂直接続と水平接続のみであるため、各ポイントには4つの隣接ポイントがあります）、ひし形が表示されます。グラフのデータ構造を実装する必要はありません。必要なのは、現在の頂点のネイバーのリストを生成することだけです。

（2）速い行進。これにより、数値誤差内の真のユークリッド距離が得られるため、ひし形ではなく、おおよその円が得られます。

于 2010-03-12T21:41:58.630 に答える
0

反復Nの場合、PからP'<= Nまでの距離（距離は| X'-X |）となるようにすべての点P'が必要です。+ |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 に答える