Поиск окрестности в матрицах

Question

Я работаю над проектом, содержащим методы клеточного автомата. Я пытаюсь понять, как написать функцию, помогающую найти всех соседей в массиве 2d. , например, я ве получил размер х размер 2d массив [SIZE = 4] здесь

[x][n][ ][n] 
[n][n][ ][n] 
[ ][ ][ ][ ] 
[n][n][ ][n] 

поле, помеченное как х [0,0] индекс имеет соседей помечены как [п] -> 8 соседей. То, что я пытаюсь сделать, - написать функцию, которая может найти соседей, которые могут быть записаны в операторы if.

Есть ли у кого-нибудь идеи, как это сделать? спасибо

Answer 1

Для соседей элемента (I, J) в матрице NXM:

int above = (i-1) % N; 
int below = (i+1) % N; 
int left = (j-1) % M; 
int right = (j+1) % M; 

decltype(matrix[0][0]) *indices[8]; 
indices[0] = & matrix[above][left]; 
indices[1] = & matrix[above][j]; 
indices[2] = & matrix[above][right]; 
indices[3] = & matrix[i][left]; 
// Skip matrix[i][j] 
indices[4] = & matrix[i][right]; 
indices[5] = & matrix[below][left]; 
indices[6] = & matrix[below][j]; 
indices[7] = & matrix[below][right]; 

Answer 2

Добавить и вычесть один из координат во всех возможных перестановках. Результаты за пределами границ обертывания (например, -1 становится 3 и 4 становится 0). Просто пара простых петель необходима в основном.

Что-то вроде

// Find the closest neighbours (one step) from the coordinates [x,y] 
// The max coordinates is max_x,max_y 
// Note: Does not contain any error checking (for valid coordinates) 
std::vector<std::pair<int, int>> getNeighbours(int x, int y, int max_x, int max_y) 
{ 
    std::vector<std::pair<int, int>> neighbours; 

    for (int dx = -1; dx <= 1; ++dx) 
    { 
     for (int dy = -1; dy <= 1; ++dy) 
     { 
      // Skip the coordinates [x,y] 
      if (dx == 0 && dy == 0) 
       continue; 

      int nx = x + dx; 
      int ny = y + dy; 

      // If the new coordinates goes out of bounds, wrap them around 
      if (nx < 0) 
       nx = max_x; 
      else if (nx > max_x) 
       nx = 0; 

      if (ny < 0) 
       ny = max_y; 
      else if (ny > max_y) 
       ny = 0; 

      // Add neighbouring coordinates to result 
      neighbours.push_back(std::make_pair(nx, ny)); 
     } 
    } 

    return neighbours; 
} 

Пример использования для вас:

auto n = getNeighbours(0, 0, 3, 3); 
for (const auto& p : n) 
    std::cout << '[' << p.first << ',' << p.second << "]\n"; 

Печатает

 
[3,3] 
[3,0] 
[3,1] 
[0,3] 
[0,1] 
[1,3] 
[1,0] 
[1,1] 

что правильный ответ.

Answer 3

Предположим, вы находитесь в камере (i, j). Затем, на бесконечной сетке, ваши соседи должны быть [(i-1, j-1), (i-1,j), (i-1, j+1), (i, j-1), (i, j+1), (i+1, j-1), (i+1, j), (i+1, j+1)].

Однако, поскольку сетка конечна, некоторые из приведенных выше значений выйдут за пределы. Но мы знаем модульную арифметику: 4 % 3 = 1 и -1 % 3 = 2. Таким образом, если сетка имеет размер n, m вам необходимо применить %n, %m в приведенном выше списке, чтобы получить надлежащий список соседей только: [((i-1) % n, (j-1) % m), ((i-1) % n,j), ((i-1) % n, (j+1) % m), (i, (j-1) % m), (i, (j+1) % m), ((i+1) % n, (j-1) % m), ((i+1) % n, j), ((i+1) % n, (j+1) % m)]

Это работает, если ваши координаты между 0 и n и между 0 и m. Если вы начинаете с 1, тогда вам нужно настроить выше, сделав -1 и +1.

Для вашего случая n=m=4 и (i, j) = (0, 0). Первый список - [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]. Применяя операции модуля, вы получаете [(3, 3), (3, 0), (3, 1), (0, 3), (0, 1), (1, 3), (1, 0), (1, 1)], которые в точности соответствуют квадратам с пометкой [n].