Как найти ячейки в сетке, которые пересекаются прямой линией?

Question

Начиная с сетки дискретизированных позиций и учитывая начальную и конечную точки для линейного сегмента, как вы будете искать ячейки в этой сетке, которые пересекаются этим линейным сегментом?

Пример:

import numpy as np

xd = np.arange(0, 20, 1)
yd = np.arange(0, 10, 1)

grid = np.full((len(xd), len(yd)), False)

set_some_grid_cells_to_True(grid)

x_start = 2.7
x_end = 4.9

y_start = 1.5
y_end = 5.7

# Here I would like to check if the straight line given by those two 
# endpoints intersects any of the cells on the grid that have the value True 

Я бы хотел, чтобы это работало систематически, независимо от начальных или конечных точек и независимо от разрешения сетки.

Answer 1

Существует специальный алгоритм, предназначенный для извлечения всех ячеек между двумя точками:
Алгоритм обхода сетки Ву и Аманатида "Алгоритм быстрого обхода вокселей ..."

Примерреализации в C

На рисунке показаны затронутые ячейки:

Answer 2

Это моя попытка ответить на ваш вопрос

пожалуйста, найдите объяснение в комментарии

Примечание: предполагается, что сетка заканчивается в 9 в направлении y

import numpy as np

xd = np.arange(0, 20, 1)
yd = np.arange(0, 10, 1)

grid = np.random.choice([True, False], (len(xd), len(yd)))

x_start = 2.7
x_end = 4.9

y_start = 1.5
y_end = 5.7


## find line equation
m = (y_end - y_start)/(x_end-x_start)
c = y_start - m*x_start

## find y value of line at all starting x of grid
y_line = m*xd + c

## find y index of cell at which line cross at each start of grid
insert_ind = yd.searchsorted(y_line)

## find x and y index of grid where line intersect
x_index, y_index = zip(*[(i,ind) for i, ind in enumerate(insert_ind) if (ind>0 and ind<len(yd)-1)])

## create grid with all False for intersecting and set intersecting cells to True
intersecting_grid = np.full((len(xd), len(yd)), False)
intersecting_grid[x_index, y_index] = True

result = intersecting_grid & grid

print(result)