Is there an easy way 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.
(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)
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
Here is a working Javascript example from @seb original pseudo code:
function findingNeighbors(myArray, i, j) {
var rowLimit = myArray.length-1;
var columnLimit = myArray[0].length-1;
for(var x = Math.max(0, i-1); x <= Math.min(i+1, rowLimit); x++) {
for(var y = Math.max(0, j-1); y <= Math.min(j+1, columnLimit); y++) {
if(x !== i || y !== j) {
console.log(myArray[x][y]);
}
}
}
}
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.
To print the neighbors of L[row][column]:
print(L[row-1][column-1], L[row-1][column], L[row-1][column+1])
print(L[row][column-1], L[row][column], L[row][column+1])
print(L[row+1][column-1], L[row+1][column], L[row+1][column+1])
That's probably the fastest/easiest way is to just print 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.
This is an implementation of @Seb's answer in python3+ that is concise and uses generators for max performance:
def neighbours(pos, matrix):
rows = len(matrix)
cols = len(matrix[0]) if rows else 0
for i in range(max(0, pos[0] - 1), min(rows, pos[0] + 2)):
for j in range(max(0, pos[1] - 1), min(cols, pos[1] + 2)):
if (i, j) != pos:
yield matrix[i][j]
Grid (vector 2D or one dimension... not the problem here)
X & Y, coordinate of your element (or just pass your vector element by ref...)
int neighbour(const Grid & g, const size_t & x, const size_t & y) {
for (int i = -1; i < 2; ++i)
for (int j = -1; j < 2; ++j)
if (x + i >= 0 && x + i < g.row && y + j >= 0 && y + j < g.col)
//Do some stuff
return 0;
}
// My approach in JS
let size = 10
//or some arbitrary number for the size of your grid.
const neighbors = [
[-1, -1],
[-1, 0],
[-1, 1],
[0, -1],
[0, 1],
[1, -1],
[1, 0],
[1, 1]
]
for (let i = 0; i < size; i++) {
for (let j = 0; j < size; j++) {
neighbors.forEach(([x, y]) => {
const newI = i + x;
const newJ = j + y;
if (
newI >= 0 &&
newI < size &&
newJ >= 0 &&
newJ < size
) {
// you can access your grid neighbors here ----> grid[newI][newJ];
}
```
I've found this approach helpful because it defines all of the array coordinates as transformations of the existing i and j indexes in your for loops.
EDIT: This "neighborhood" of cells around a specified cell in a 2D matrix is actually called a [Moore Neighborhood][1] and is used in cellular automata. Fun!
[1]: https://en.wikipedia.org/wiki/Moore_neighborhood
Here is a convenient method in Python:
def neighbors(array,pos):
n = []
string = "array[pos.y+%s][pos.x+%s]"
for i in range(-1,2):
for j in range(-1,2):
n.append(eval(string % (i,j)))
return n
Assuming pos is some 2D Point object and array is a 2D array.
Since in a matrix around an element there are only 8 elements, you can use array to store different index values.For e.g.,
int iarr[8] = {-1,-1,-1,0,0,+1,+1,+1};
int jarr[8] = {-1,0,+1,-1,+1,-1,0,+1};
for(int i = 0 ; i < 8 ; i++)
{
if(arr[x-iarr[i]][y-jarr[i]] == 1)
{
//statements
}
}
/* x and y are the position of elements from where you want to reach out its neighbour */
since both array contains just 8 values , then space might not be a problem.
The approach I usually take is described on the bottom of this blog: https://royvanrijn.com/blog/2019/01/longest-path/
Instead of hardcoding the directions or having two nested loops I like to use a single integer loop for the 8 ‘directions’ and use (i % 3)-1 and (i / 3)-1; do check out the blog with images.
It doesn’t nest as deep and is easily written, not a lot of code needed!
JS sample :
function findingNeighbors(myArray, i, j){
return myArray.reduce(function(a, b, c){
if(Math.max(0, i-1) <= c && c <= Math.min(i+1, myArray.length-1)){
a = a.concat(
b.reduce(function(d, e, f){
if(f == j && c == i)
return d;
if(Math.max(0, j-1) <= f && f <= Math.min(j+1, myArray.length-1))
d.push(e)
return d;
},[])
);
}
return a;
},[]);
}
private ArrayList<Element> getNeighbors(Element p) {
ArrayList<Element> n = new ArrayList<Element>();
for (int dr = -1; dr <= +1; dr++) {
for (int dc = -1; dc <= +1; dc++) {
int r = p.row + dr;
int c = p.col + dc;
if ((r >= 0) && (r < ROWS) && (c >= 0) && (c < COLS)) {
// skip p
if ((dr != 0) || (dc != 0))
n.add(new Element(r, c));
}
}
}
return n;
}
although nested for loops in list comprehensions is a bit ugly this is shorter:
def neighbours(m, i, j):
return [m[x][y] for x in [i-1,i,i+1] for y in [j-1,j,j+1] if x in range(0,len(m)) and y in range(0,len(m[x])) and (x,y) != (i,j)]
here is some code for C#:
public Cell[,] MeetNeigbours(Cell[,] Grid)
{
for (int X = 0; X < Grid.GetLength(0); X++)
{
for (int Y = 0; Y < Grid.GetLength(1); Y++)
{
int NeighbourCount = 0;
for (int i = -1; i < 2; i++)
{
for (int j = -1; j < 2; j++)
{
if (CellExists(Grid, (X + i)), (Y + j) && (i != 0 && j != 0))
{
Grid[X, Y].Neighbours[NeighbourCount] = Grid[(X + i), (Y + j)];
}
if(!(i == 0 && j == 0))
{
NeighbourCount++;
}
}
}
}
}
return Grid;
}
public bool CellExists(Cell[,] Grid, int X, int Y)
{
bool returnValue = false;
if (X >= 0 && Y >= 0)
{
if (X < Grid.GetLength(0) && Y < Grid.GetLength(1))
{
returnValue = true;
}
}
return returnValue;
}
with the "Cell" class looking like this:
public class Cell
{
public Cell()
{
Neighbours = new Cell[8];
}
/// <summary>
/// 0 3 5
/// 1 X 6
/// 2 4 7
/// </summary>
public Cell[] Neighbours;
}
Rows and Cols are total number of rows and cols
Define a CellIndex struct or class. Or you can just return the actual values instead of the indexes.
public List<CellIndex> GetNeighbors(int rowIndex, int colIndex)
{
var rowIndexes = (new int[] { rowIndex - 1, rowIndex, rowIndex + 1 }).Where(n => n >= 0 && n < Rows);
var colIndexes = (new int[] { colIndex - 1, colIndex, colIndex + 1 }).Where(n => n >= 0 && n < Cols);
return (from row in rowIndexes from col in colIndexes where row != rowIndex || col != colIndex select new CellIndex { Row = row, Col = col }).ToList();
}
This was really helpful to me in a recent project, so here's @Seb 's pseudo-code implementation in swift. This is assuming that the two-dimensional array is square:
func adjacentIndexPaths(to indexPath: IndexPath) -> [IndexPath] {
var neighboringSquareIndexes: [IndexPath] = []
// gridSquareCount is the size of the 2D array. For example, in an 8 x 8 [[Array]], gridSquareCount is 8
let maxIndex = gridSquareCount - 1
var neighborRowIndex = max(0, indexPath.section - 1)
var neighborColumnIndex = max(0, indexPath.row - 1)
while neighborRowIndex <= min(indexPath.section + 1, maxIndex) {
while neighborColumnIndex <= min(indexPath.row + 1, maxIndex) {
if neighborRowIndex != indexPath.section || neighborColumnIndex != indexPath.row {
neighboringSquareIndexes.append(IndexPath(row: neighborColumnIndex, section: neighborRowIndex))
}
neighborColumnIndex += 1
}
neighborRowIndex += 1
neighborColumnIndex = max(0, indexPath.row - 1)
}
return neighboringSquareIndexes }
In javascript
let arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
function getNeighborsNumbersAtIthJth(i, j) {
let allPosibleIndexes = [
[i - 1, j],
[i, j - 1],
[i - 1, j - 1],
[i + 1, j],
[i, j + 1],
[i + 1, j + 1],
[i + 1, j - 1],
[i - 1, j + 1]
];
let allPosibleValues = []
allPosibleIndexes.forEach(([i, j]) => {
try {
allPosibleValues.push(arr[i][j])
} catch (err) {
}
})
return allPosibleValues.filter(v => v != undefined);
}
console.log(getNeighborsNumbersAtIthJth(1, 1));//[2, 4, 1, 8, 6, 9, 7, 3]
console.log(getNeighborsNumbersAtIthJth(0, 1));//[1, 5, 3, 6, 4]
console.log(getNeighborsNumbersAtIthJth(0, 0));//[4, 2, 5]
I use a directions array and run a loop to get appropriate directions. Something like this (code is in JS)
function getAdjacent(matrix, i, j, k) {
const directions = [
[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],
];
const [row, col] = directions[k];
// Check for last rows and columns
if (row < 0 || row >= matrix.length || col < 0 || col >= matrix[i].length) {
return undefined;
}
return matrix[row][col];
}
function run(){
const hello = 'hello';
const matrix = [
[1, 2, 1],
[2, 1, 1],
[1, 1, 1]
];
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[i].length; j++) {
let sum = 0;
for (let k = 0; k < 8; k++) {
const res = getAdjacent(matrix, i, j, k);
console.log(i, j, k, res); // Do whatever you want here
}
}
}
}
run();
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.
This example in Python might also shed some light:
from itertools import product
def neighbors(coord: tuple, grid=(10, 10), diagonal=True):
"""Retrieve all the neighbors of a coordinate in a fixed 2d grid (boundary).
:param diagonal: True if you also want the diagonal neighbors, False if not
:param coord: Tuple with x, y coordinate
:param grid: the boundary of the grid in layman's terms
:return: the adjacent coordinates
"""
width = grid[0] - 1
height = grid[1] - 1
retx, rety = coord
adjacent = []
nb = [x for x in product([-1, 0, 1], repeat=2) if x != (0, 0)]
if not diagonal:
nb = [x for x in nb if x not in product([-1, 1], repeat=2)]
for x, y in nb:
xx = retx + x
yy = rety + y
if xx < 0 or xx > width or yy < 0 or yy > height:
# not within its boundaries
continue
adjacent.append((xx, yy))
return adjacent
the first product line (nb = [x for x in product([-1, 0, 1], repeat=2) if x != (0, 0)]) will produce all the coordinates of its neibors including the diagonal ones. The (0,0) is removed because that is ourselves so not a neighbor :-)
[(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
If you do not want the diagonal neighbors you can tell it to remove those (product([-1, 1], repeat=2)) then the boundaries of the grid are checked and the resulting list of coordinates will be produced.
Ruby => Returns an array of neighbours.
array = [
[1, 2, 5, 6],
[8, 89, 44, 0],
[8, 7, 23, 0],
[6, 9, 3, 0]
]
def neighbours(array, (i , j))
[
[i, j - 1],
[i, j + 1],
[i - 1, j - 1],
[i - 1, j],
[i - 1, j + 1],
[i + 1, j - 1],
[i + 1, j],
[i + 1, j + 1],
].select { |h, w|
h.between?(0, array.length - 1) && w.between?(0, array.first.length - 1)
}.map do |row, col|
array[row][col]
end
end
array.each_with_index do |row, i|
row.each_with_index do |col, j|
p(array[i][j], neighbours(array, [i, j]))
end
end
I know this is an older question. However, I want to post a solution that I wrote based on Shubh Tripathi's answer
If we're looking for the same neighbors every time and want efficient bounds checking, there is a simple way to achieve this by just storing the indexes we want in an array without re-generating them in each iteration.
I wrote this for a simulation, where I wanted to check all directions surrounding an entity.
def get_surroundings(self, position):
"""
For a given grid location, it returns the surrounding 8x8 grid.
Indexed from the top left to the bottom right. (row-wise)
Args:
position (tuple): The position of the grid location.
Returns:
list: The surrounding 8x8 grid.
"""
# set the x and y coordinates
x = position[0]
y = position[1]
# list out the relative locations of the neighbors
surroundings = [
(-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 1),
(1, -1), (1, 0), (1, 1)
]
return_list = []
# go through the relative neighbours list, and check if any of the
# bounds condition fail. if they do, append none.
for neighbour in surroundings:
if (
x + neighbour[0] < 0 or
x + neighbour[0] >= self.grid_size or
y + neighbour[1] < 0 or
y + neighbour[1] >= self.grid_size
):
return_list.append(None)
else:
return_list.append(self.grid[x + neighbour[0]][y + neighbour[1]])
self.grid is your 2x2 grid.
let push = (array,i,j) => (array[i] && array[i][j]) ? res.push(array[i][j]) : "cant"
let index = [-1,0,1]
function neighbours(arr,i,j){
let res =[];
let x,y;
for(y=0;y<3;y+=2){ // +2 to skip the row of element in question
for(x=0;x<3;x++){
push(array,i+index[y],j+index[x])
}
}
push(array,i,j+1)
push(array,i,j-1)
}
here we want to push
I struggled for a bit on this and came up with being able to use list comprehension to work well. It does require the use of numpy to add offsets to the original array.
There are possibilities of 3, 5, or 8 neighbors, depending on a corner, edge, or an embedded cell deeper in the array. Like some of the other solutions provided, this solution also allows for solving different sizes of arrays.
You obtain two array results: newpos and newrow by adding the offsets to an existing cell position:
pos = np.array([5,5]) # Current position
shape = [6,6] # Shape of array
newpos = diff + pos[1] # Previous position, current position, next position
newrow = diff + pos[0]
The list comprehension is very powerful. It checks for values in newrows for r in newrow as well as values in newpos for p in newpos.
Theif condition filters those results:
not (r == newrow[1] and p == newpos[1]) ignores the current row and position(r >=0 and p >= 0 ignores negative values ```r < shape[0]and p < shape[1]) only shows values that reside inside the shape shape = [6,6] import numpy as np # Need to use numpy arrays
diff = np.array([-1,0,1]) # Offsets (Previous, current, next)
pos = np.array([5,5]) # Current position
shape = [6,6] # Shape of array
newpos = diff + pos[1] # Previous position, current position, next position
newrow = diff + pos[0] # Previous row, current row, next row
print (newrow, newpos) # Show new row and position lists
# Use list comprehension to show neighbors
print([[r, p] for r in newrow \
for p in newpos \
if not (r == newrow[1] and p == newpos[1]) \
and (r >=0 and p >= 0 \
and r < shape[0] \
and p < shape[1])])
