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]
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.
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.
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
