Finding Neighbourhood in Matrices [duplicate]

Question

This question already has an answer here:

Conway's Game of Life, counting neighbors [closed] (1 answer)

Closed 8 years ago.

I am working on project containing cellular automat methods. What I am trying to figure is how to write function helping to find all the neighbours in a 2d array. for example i ve got size x size 2d array [size = 4 here]

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

Field marked as x [0,0 index] has neighbours marked as [n] -> 8 neighbours. What Im trying to do is to write a function which can find neighbours wo writting tousands of if statements

Does anybody have an idea how to do it ? thanks

Answer 1

For the neighbours of element (i,j) in NxM matrix:

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

Suppose you are in cell (i, j). Then, on an infinite grid, your neighbors should be [(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)].

However, since the grid is finite some of the above values will get outside the bounds. But we know modular arithmetic: 4 % 3 = 1 and -1 % 3 = 2. So, if the grid is of size n, m you only need to apply %n, %m on the above list to get the proper list of neighbors: [((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)]

That works if your coordinates are between 0 and n and between 0 and m. If you start with 1 then you need to tweak the above by doing a -1 and a +1 somewhere.

For your case n=m=4 and (i, j) = (0, 0). The first list is [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]. Applying the modulus operations you get to [(3, 3), (3, 0), (3, 1), (0, 3), (0, 1), (1, 3), (1, 0), (1, 1)] which are exactly the squares marked [n] in your picture.

Answer 3

Add and subtract one from the coordinates, in all possible permutations. Results outside the boundaries wrap around (e.g. -1 becomes 3 and 4 becomes 0). Just a couple of simple loops needed basically.

Something like

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

Example use for you:

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

Prints out

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

which is the correct answer.