As you can see, there is a 10 by 10 grids. They are stored in a variable matrix.
The matrix stores an 10 by 10 2 dimensional array. In each element, the data structure looks like:
{ "distance": distance, "topLeft": (xmin, ymin), "bottomRight": (xmax, ymax) }
We also know X1(x1,y1), X2(x2, y2).
Question:
How can I find out all grids which have the path(X1 to X2) inside?
E.g. matrix[0][7] has a part of the path, thus it should be included in the result array.
Update 1
One thing to mention that: this code will be running during a video stream on RPi, so I prefer the algorithm does need to go through each pixel to figure out whether a cell includes the path or not.
Update2:
One important thing I need to mention: the X1, X2 are the points in an 224 by 224 image.
I'm now using the Bresenham's line algorithm. The code generates X,y coordinates on my image, but what I Really need to know is which grid is crossed by the line. So how can I utilise the Bresenham's line algorithm to get the crossed grids?
Update 3
Here is the Python Code I implemented for the Bresenham's_line_algorithm
def _find_crossed_cells(self, point0, point1, matrix) -> List(tuple):
path_cells = []
x0, y0 = point0
x1, y1 = point1
dx = abs(x1 - x0)
sx = 1 if x0 < x1 else -1
dy = abs(y1 - y0)
sy = 1 if y0 < y1 else -1
error = dx + dy
while True:
path_cells.append((x0, y0))
if x0 == x1 and y0 == y1:
break
e2 = 2 * error
if e2 >= dy:
if x0 == x1:
break
error = error + dy
x0 = x0 + sx
if e2 <= dx:
if y0 == y1:
break
error += dx
y0 += sy
return path_cells
As you can see this code can only find a list of x,y coordinates(224 by 224), but I need to find out a lit of crossed cells(10 by 10 coordinates). So how can I achieve this?
