Finding neighbors in a two-dimensional array

Neighbor searching in programming is the process of finding elements that are adjacent to a given element in a data structure (such as a matrix or graph). This approach is used to analyze the relationships between elements, determine their properties based on the environment, and perform various algorithms (for example, path finding, clustering, data filtering).

In the case of a two-dimensional matrix, neighbors of an element usually mean elements that are located directly horizontally, vertically and/or diagonally relative to a given element. For example, for a matrix of size N×Melement with coordinates (i,j) can have up to 8 neighbors (if you count the diagonals).

A comprehensive search for neighbors in a matrix may be needed in a number of tasks:

• Pathfinding algorithms (graphs, labyrinths)

• Algorithms for filling areas (for example, filling with paint)

• Image processing

• Games on cellular fields (for example, “Mineweeper”)

• Data clustering

• Simulation of physical processes

• Cluster search algorithms (for example, DBSCAN)

• Processing text and character data

Thus, a comprehensive search for neighbors allows you to effectively solve problems where you need to analyze not only local data at one point, but also its surroundings.

Before we continue, I want to invite you to my telegram channel Don Pythonwhere I share interesting features of the language, non-obvious tricks and solve various problems.

Subscribe

The simplest example

def get_neighbors(matrix, row, col):
	rows = len(matrix)
	cols = len(matrix[0])
	
	directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
	
	neighbors = []
	
	for dr, dc in directions:
		new_row, new_col = row + dr, col + dc
		
		if 0 <= new_row < rows and 0 <= new_col < cols:
			neighbors.append(matrix[new_row][new_col])
			
	return neighbors
	
	
matrix = [
	[1, 2, 3],
	[4, 5, 6],
	[7, 8, 9]
]

neighbors = get_neighbors(matrix, 1, 1)
print("Neighbors of element at (1,1):", neighbors)

# >>> Neighbors of element at (1,1): [2, 8, 4, 6, 1, 3, 7, 9]

Explanation

1. We start with a function declaration get_neighbors with parameters:

• matrix – matrix to work with

• row – row index

• col – column index

2. Get the matrix size rows × cols

3. Array directions contains all possible directions for searching neighbors in a two-dimensional matrix.

Each element of this array is a tuple (a pair of numbers), where:

These pairs are used to offset an element's current position in a two-dimensional matrix.

If you randomly print the array directions and superimpose it on the matrix, you can get the following picture:

(-1, -1) (-1, 0) (-1, 1)
(0, -1)  (i, j)  (0, 1)
(1, -1)  (1, 0)  (1, 1)

Here:

• Center (i,j) is the current position of the element.

• Each pair of numbers from the array directions indicates one of the cells around this element.

4. Create an array neighbors. In the future we will fill it with all the neighbors we find.

5. And immediately return the array neighborsomitting the main search algorithm for now.

Let's see what is happening at the moment:

def get_neighbors(matrix, row, col):
	rows = len(matrix)
	cols = len(matrix[0])
	
	directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
	
	neighbors = []
	
	return neighbors

6. Now let's move on to writing the algorithm. Let's go through the cycle for by array directions and print each tuple into two variables: dr, dc.

7. In the first line of the loop, for each direction we calculate a new position (row and column) and check whether they are within the matrix. We do this by adding the row index (row) with the value of the variable dr and adding the column index (col) with the value of the variable dc.

The process looks like this:

We are standing on cell (1,1) and want to check our neighbors in different directions.

• Direction (−1,0) – upward movement: the new position will be (0,1).

• Direction (1,0) – downward movement: the new position will be (2,1).

• Direction (0,−1) – movement to the left: the new position will be (1,0).

• Direction (0,1) – movement to the right: the new position will be (1,2).

If we were to move diagonally:

• Direction (−1,−1) is the new position (0,0).

• Direction (1,1) – new position (2,2).

8. Now, using the condition, we need to determine whether the position we want to access is within the matrix. To do this you need to make sure that the value new_row ranges from 0 to len(matrix) And new_col in the range from 0 to len(matrix[0]).

9. If the condition is true, then we can claim that the position we want to access is accessible and is adjacent to the position from which we started the search. Adding the position value to the array neighbors. If the condition is not true, move on to the next iteration.

Working function:

def get_neighbors(matrix, row, col):
	rows = len(matrix)
	cols = len(matrix[0])
	
	directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
	
	neighbors = []
	
	for dr, dc in directions:
		new_row, new_col = row + dr, col + dc
		
		if 0 <= new_row < rows and 0 <= new_col < cols:
			neighbors.append(matrix[new_row][new_col])
			
	return neighbors

10. All we have to do is create an arbitrary matrix, call the function, get an array of neighbors and display the result:

matrix = [
	[1, 2, 3],
	[4, 5, 6],
	[7, 8, 9]
]

neighbors = get_neighbors(matrix, 1, 1)
print("Neighbors of element at (1,1):", neighbors)

You can go back to the main block of code and re-analyze all the steps.

Practical example. Blur the picture

I propose to see in practice what can be done using the neighbor search method, as well as find out how you can expand the search radius.

One simple and practical example of using neighbor search in a two-dimensional array is image filtering. In this task, we can use an algorithm to process pixel values ​​to, for example, blur the image or apply an edge detector.

Let us introduce some restrictions to simplify and clarify the example:

• The image is no larger than 256×256

• The picture must be black and white

• There will not be a detailed analysis of how converting an image into a matrix and back works. I'll just post the working code

I chose the following picture:

The blurring process consists of 3 main stages:

1. Converting an image into a matrix

2. Creating a Blur Filter

3. Converting a matrix back to an image

Initial file structure:

blur_img
	img.jpg
	main.py

Converting an image into a matrix

Install the required library:

pip install Pillow

We use the following code to create the conversion function:

from PIL import Image

def itm(*, image_path):  
    # Открываем изображение  
    img = Image.open(image_path)  
  
    # Преобразуем изображение в режим "L" (оттенки серого)  
    img = img.convert("L")  
  
    # Получаем размеры изображения  
    width, height = img.size  
  
    # Создаём матрицу  
    matrix = []  
  
    for y in range(height):  
        row = []  
        for x in range(width):  
            # Получаем значение пикселя  
            pixel_value = img.getpixel((x, y))  
            row.append(pixel_value)  
        matrix.append(row)  
  
    return matrix

Next we will use this function as an imported module. To do this, let's change our file structure:

blure_img
	image_conversion
		image_to_matrix.py
	img.jpg
	main.py

Blur function

In this example, we will use a matrix representing an image, where each value is the intensity of a pixel (for example, from 0 to 255 for a gray image). We'll apply a blur filter that replaces the value of each pixel with the average of its neighbors.

from image_conversion.image_to_matrix import itm    
  
def apply_blur_filter(image):  
    rows = len(image)  
    cols = len(image[0])  
  
    blurred_image = [[0] * cols for _ in range(rows)]  
  
    directions = [(-1, -1), (-1, 0), (-1, 1),  
                  (0, -1), (0, 0), (0, 1),  
                  (1, -1), (1, 0), (1, 1)]  

    for i in range(rows):  
        for j in range(cols):  
            pixel_sum = 0  
            count = 0  
  
            for dx, dy in directions:  
                new_x, new_y = i + dx, j + dy  
  
                if 0 <= new_x < rows and 0 <= new_y < cols:  
                    pixel_sum += image[new_x][new_y]  
                    count += 1  
  
            blurred_image[i][j] = pixel_sum // count  
  
    return blurred_image  
  

matrix = itm(image_path="img.jpg") 

blurred_image = apply_blur_filter(matrix)

We are already familiar with this function, but in the basic example we found neighbors for only one specified element, and now we need to find neighbors for all elements of the matrix. To do this, we initialize two loops that will process each pixel of the image (matrix element).

At the neighbor search level, 3 new lines will be added:

• pixel_sum – the sum of the values ​​of all neighboring pixels

• count – number of neighbors of the current pixel

• blurred_image[i][j] = pixel_sum // count – calculation and assignment of a new value

As a result, we get a new matrix with changed values, which we need to convert into an image.

Converting a matrix into a picture

To save the matrix back into the image we will use the installed library Pillow. The inverse conversion process involves creating a new image from a matrix of pixels and saving it into the desired format.

from PIL import Image  
  
def mti(matrix, output_path):  
    # Получаем размеры матрицы (высота и ширина изображения)  
    height = len(matrix)  
    width = len(matrix[0])  
  
    # Создаём новое изображение в режиме RGB  
    img = Image.new("L", (width, height))  
  
    # Заполняем изображение пикселями из матрицы  
    for y in range(height):  
        for x in range(width):  
            img.putpixel((x, y), matrix[y][x])  # Устанавливаем пиксель  
  
    # Сохраняем изображение
    img.save(output_path)

Updated file structure:

blure_img
	image_conversion
		image_to_matrix.py
		matrix_to_image.py
	img.jpg
	main.py

Importing the function mti V main.py and call with the necessary parameters at the end of the code:

from image_conversion.image_to_matrix import itm
from image_conversion.matrix_to_img import mti
  
def apply_blur_filter(image):... 


matrix = itm(image_path="img.jpg") 

blurred_image = apply_blur_filter(matrix)

mti(matrix=blurred_image, output_path="blur_img.jpg")

We execute the main.py file and get the result.

Was:

Became:

Updated file structure:

blure_img
	image_conversion
		image_to_matrix.py
		matrix_to_image.py
	blur_img.jpg
	img.jpg
	main.py

Search for neighbors within an arbitrary radius

Let's assume that the previous result is not enough for us. I would like to adjust the degree of blur. To do this, it is not enough to find the nearest neighbors. It is necessary to increase the search radius.

The functions for obtaining a matrix from an image and saving the matrix as an image remain unchanged. We need to make some small changes to the function apply_blur_filter.

Let's look at the changes:

def apply_blur_filter(image, blur_radius=2):  
    rows = len(image)  
    cols = len(image[0])  
  
    blurred_image = [[0] * cols for _ in range(rows)]  
  
    offset_range = range(-blur_radius, blur_radius + 1) 

    for i in range(rows):  
        for j in range(cols):  
            pixel_sum = 0  
            count = 0  
  
            for dx in offset_range:  
			    for dy in offset_range: 
	                new_x, new_y = i + dx, j + dy  
	  
	                if 0 <= new_x < rows and 0 <= new_y < cols:  
	                    pixel_sum += image[new_x][new_y]  
	                    count += 1  
  
            blurred_image[i][j] = pixel_sum // count  
  
    return blurred_image  

Explanation

1. Add a new argument to the function parameters blur_radius

2. Now instead of an array directions with coordinates to find nearest neighbors, we will use the range from -blur_radius to blur_radius + 1. At blur_radius=2 by default the range will be like this: [-2, -1, 0, 1, 2]

3. The most significant change was the addition of a fourth cycle. Now the variables dx And dy are not used within the same cycle, where we traversed neighboring pixels relative to the current one. Now dx represents the coordinate on the axis xrelative to which the axis is traversed y in the range offset_range.

I suggest you delve a little into the subtleties

For each pixel we need to calculate a new value, which will be the average over the area blur_radius + (blur_radius + 1) x blur_radius + (blur_radius + 1)which includes this pixel. If the blur radius is 2, then we will consider all neighbors within 2 pixels of the current one, that is, a 5×5 area.

Let's say we have the following matrix of pixel brightness or color values:

[
    [10, 20, 30, 40, 50, 60],
    [15, 25, 35, 45, 55, 65],
    [20, 30, 40, 50, 60, 70],
    [25, 35, 45, 55, 65, 75],
    [30, 40, 50, 60, 70, 80],
    [35, 45, 55, 65, 75, 85]
]

Let the coordinates of the current pixel be (2, 2). For a pixel with coordinates (2,2) and value 40the 5×5 blur area includes the following pixels:

[
    [10, 20, 30, 40, 50],  # Соседи сверху
    [15, 25, 35, 45, 55],  # 2 строка
    [20, 30, 40, 50, 60],  # Строка с текущим пикселем (2,2)
    [25, 35, 45, 55, 65],  # 4 строка
    [30, 40, 50, 60, 70]   # Соседи снизу
]

In this case, the axis x represented by a string [20, 30, 40, 50, 60]. Given the search range [-2, -1, 0, 1, 2]we can understand that the cycle for dx in offset_range will process every pixel in this line. At each iteration of the loop for dxcycle for dy in offset_range will process all values ​​along the axis y in the same range [-2, -1, 0, 1, 2]. Thus, if on the axis x the current coordinate is (-2, 0), which corresponds to pixel (2, 0) in the matrix, then the loop for dy will process all values ​​in the column [10, 15, 20, 25, 30].

After applying blur to each pixel based on its neighbors, the resulting matrix might look something like this:

[
    [25, 30, 35, 40, 45, 50],
    [30, 35, 40, 45, 50, 55],
    [35, 40, 40, 45, 50, 60],
    [40, 45, 45, 50, 55, 65],
    [45, 50, 50, 55, 60, 70],
    [50, 55, 60, 65, 70, 75]
]

Blur algorithm with radius blur_radius = 2 averages the values ​​for a 5×5 area around each pixel. Pixels at the edges of the matrix take into account a smaller number of neighbors (due to the fact that part of the area extends beyond the boundaries of the image). As a result, we get a “blurred” version of the original matrix, where each pixel is replaced by the average value of its neighbors.

I propose to evaluate the result of blur with an arbitrary radius, where blur_radius=2:

Was:

Became:

Results

The following task prompted me to write this article: https://dmoj.ca/problem/coci13c2p2

Thank you for reading, I encourage constructive criticism and discussion in the comments.

Peace to all!