Finding neighbours in a two-dimensional array

Question

Is there an easy way of finding of finding the neighbours (that is, the eight elements around an element) of an element in a two-dimensional array? Short of just subtracting and adding to the index in different combinations, like this:

array[i-1][i]
array[i-1][i-1]
array[i][i-1]
array[i+1][i]

... And so on.

Answer 1

array[i][j] has neighbors

array[i-1][j]
array[i][j-1]
array[i-1][j-1]
array[i+1][j]
array[i][j+1]
array[i+1][j+1]
array[i+1][j-1]
array[i-1][j+1]

That's probably the fastest/easiest way is to just list all possible neighbors. Make sure to do index out of bound checking though.

Some languages might offer a shortcut way of doing this, but I don't know of any.

Answer 2

(pseudo-code)

row_limit = count(array);
if(row_limit > 0){
  column_limit = count(array[0]);
  for(x = max(0, i-1); x <= min(i+1, row_limit); x++){
    for(y = max(0, j-1); y <= min(j+1, column_limit); y++){
      if(x != i || y != j){
        print array[x][y];
      }
    }
  }
}

Of course, that takes almost as many lines as the original hard-coded solution, but with this one you can extend the "neighborhood" as much as you can (2-3 or more cells away)

Answer 3

A lot depends on what your data is. For example, if your 2D array is a logical matrix, you could convert rows to integers and use bitwise operations to find the ones you want.

For a more general-purpose solution I think you're stuck with indexing, like SebaGR's solution.

Answer 4

an alternative to @SebaGR, if your language supports this:

var deltas = { {x=-1, y=-1}, {x=0, y=-1}, {x=1, y=-1},
               {x=-1, y=0},               {x=1, y=0},
               {x=-1, y=1},  {x=0, y=1},  {x=1, y=1} };
foreach (var delta in deltas)
{
    if (x+delta.x < 0 || x + delta.x >= array.GetLength(0) ||
        y+delta.y < 0 || y + delta.y >= array.GetLength(1))
        continue;

    Console.WriteLine("{0}", array[x + delta.x, y + delta.y]);
}

Slight advantage in readability, possible performance if you can statically allocate the deltas.

Answer 5

I think Ben is correct in his approach, though I might reorder it, to possibly improve locality.

array[i-1][j-1]
array[i-1][j]
array[i-1][j+1]

array[i][j-1]
array[i][j+1]

array[i+1][j-1]
array[i+1][j]
array[i+1][j+1]

One trick to avoid bounds checking issues, is to make the array dimensions 2 larger than needed. So, a little matrix like this

3 1 4
1 5 9
2 6 5

is actually implemented as

0 0 0 0 0
0 3 1 4 0
0 1 5 9 0
0 2 6 5 0
0 0 0 0 0

then while summing, I can subscript from 1 to 3 in both dimensions, and the array references above are guaranteed to be valid, and have no effect on the final sum. I am assuming c, and zero based subscripts for the example