Authors Top

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.


1. Introduction

In this tutorial, we’ll show how to find neighbors of a cell in a two-dimensional matrix.

2. Neighbors

Let’s say we have an m \times n matrix A. We want to get all the neighbors of \boldsymbol{A[i, j]}, the cell in the \boldsymbol{i}-th row and \boldsymbol{j}-th column (1 \leq i \leq m, 1 \leq j \leq n).

Usually, we define a cell’s neighbors as all the cells it borders with horizontally, vertically, or diagonally:

Neighbors

The vertical neighbors of A[i, j] are A[i - 1, j] and A[i + 1, j]. They’re in the same column as A[i, j], right above and below it. Similarly, its horizontal neighbors are A[i, j - 1] and A[i, j + 1]: the cells right to its left and right.

The diagonal neighbors are in the corners of the neighborhood square. The top left is A[i - 1, j - 1], the top right A[i - 1, j + 1], the bottom left is A[i + 1, j - 1], and the bottom right A[i + 1, j + 1].

3. Iterating Over Neighbors

From the above, it follows that we can iterate over all the combinations of \boldsymbol{i-1, i, i+1} and \boldsymbol{j-1, j, j+1} to get the neighbors of \boldsymbol{A[i, j]}. In doing so, we need to take care of two things.

First, it makes no sense to return \boldsymbol{A[i, j]} as its own neighbor, so we’ll omit the combination (i,j). Additionally, if \boldsymbol{A[i, j]} is at a border, some combinations will be illegal since they’ll be outside the matrix, so we need to skip them. For example, if j=n, there are no neighbors to the right of A[i, n]:

Cell at a border

Taking those two points into account, we get the neighbors of A[i, j] as follows:

Rendered by QuickLaTeX.com

A problem with this approach is that the neighborhood is hard-coded. So, if we want to define neighbors differently, we need to change the loops. Depending on the neighborhood definition, that can be cumbersome and prone to errors.

4. Iterating Over Offsets

A more flexible approach is to iterate over offsets. For instance, the offset of A[i-1, j+1] to A[i, j] is (-1, +1). So, if we have the offsets, we can iterate over them to get the neighbors of A[i, j]:

Rendered by QuickLaTeX.com

We can define a neighborhood in various ways:

Various neighborhoods

Although more flexible, this approach requires us to generate the offsets first. One way to do so is to use the corresponding distance function. For example, the Manhattan distances in the standard neighborhood are either 1 or 2. So, the offsets are in the set:

    \[\left\{ (\Delta i, \Delta j) \in \{-1, 0, 1\}^2 \mid \Delta i + \Delta j \in \{1, 2\} \right\}\]

We can also plug in the boundary checks so that all the offsets are safe:

    \[\left\{ (\Delta i, \Delta j) \in \{-1, 0, 1\}^2 \mid \Delta i + \Delta j \in \{1, 2\} \,\, \land \,\, 1 \leq i + \Delta i \leq m \,\, \land \,\, 1 \leq j + \Delta j \leq n \right\}\]

In that case, we don’t need any checks in the above algorithm.

5. Conclusion

In this article, we showed how to find neighbors of a cell in a 2D matrix.

Authors Bottom

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

Comments are closed on this article!