Алгоритм поиска радиальной сетки

Question

Я уверен, что есть чистый способ сделать это, но я, вероятно, не использую правильные ключевые слова для его поиска.

Итак, скажем, у меня есть сетка. Начиная с позиции в сетке, верните все координаты сетки, которые находятся в пределах заданного расстояния. Поэтому я называю что-то вроде:

getCoordinates( currentPosition, distance )

И для каждой координаты, начиная с начальной позиции, добавьте все кардинальные направления, а затем добавьте пробелы вокруг них и так далее, пока расстояние не будет достигнуто. Я представляю, что на сетке это будет выглядеть как алмаз. Функция вернет этот массив координат. Может кто-нибудь указать мне на рутину, которая будет делать это эффективно (я работаю в AS3, для чего это стоит)?

В желаемом выводе итерация 1 будет:

.x.
xxx
.x.

Итерация 2 будет:

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

Итерация 3:

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

и так далее ...

Answer 1

Редактировать: Обновлен алгоритм, чтобы отразить то, что хотел ОП.

Итерация 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.
        }
    }
}

Answer 2

Это зависит от того, какую структуру данных вы используете для представления вашей сетки, но обычно поиск в ширину должен позаботиться об этом за вас.

Answer 3

Я понимаю, что этому вопросу 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
            }
    }

Answer 4

Для итерации N вы хотите, чтобы все точки P 'были такими, чтобы расстояние от P до P' <= N, где расстояние равно | X '- X | + | Y '- Y |. </p>

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;

Answer 5

Две возможности, в зависимости от того, какие роды дистанции вы хотите и сколько программ вы хотите сделать:

(1) Алгоритм Дейкстры . Если вы представите, что каждые две соседние точки на вашей сетке связаны (только вертикальные и горизонтальные соединения, поэтому у каждой точки есть 4 соседа), вы получите свой ромб. Вам не нужно реализовывать какую-либо структуру данных для графа - вам нужно только генерировать списки соседей для текущей вершины по ходу работы.

(2) Быстрый марш . Это даст вам истинное евклидово расстояние в пределах числовой ошибки, так что вы получите приблизительный круг, а не ромб.

Answer 6

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;
    }    
}