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

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

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

Итерация 1:

.x. 
xxx 
.x. 

Итерация 2:

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

... Итерация 4:

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

Очевидно, что вы можете определить координаты без перебора.

Если начальная точка (X, Y), и итерация п

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

Это зависит от того, какие данные st ructure, который вы используете для представления своей сетки, но обычно breadth-first search должен позаботиться об этом для вас.

Answer 3

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

Answer 4

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

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

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

Answer 5

Для Итерации 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;