# How to find all squares over which a line passes in a finite squared tessellation of the cartesian plane?

Say we have a finite tessellation of a subsection of the Cartesian plane. In other words we have a finite grid, or a "chess board". We also have an arbitrary line defined parametrically as: $(O,\vec v)$ where $O$ is a point and $\vec v$ is a vector.

Trivially, there exists a finite number of squares over which the line passes, and it's also not all of them. Assuming that I know the dimensions of each square (say side length is 1 for simplicity) I need to know all the squares in the grid over which the line passes.

EDIT:

It is imperative to use the parametric representation for these issue, implicit equations are not suitable for some reasons (the major one being that lines cannot be defined with a single implicit equation in 3D if I wish to extend the solution to those dimensions) The above is the important part, this is optional but ideal.

I need to be able to algorithmically iterate through these squares, sequentially and in order, such that I only visit a square once in the entire algorithm.

Now, here is a simple method for solving (1), assuming the line $L$ is given by the equation $ax+by+c=0$. Define a function: $$f(x,y)= ax+by+c$$ A square $ABCD$ is crossed by the line $L$ if and only if two of its diagonally opposite vertices are separated by the line $L$. To check whether any two points $P_1$ and $P_2$ are separated by line $L$, we can simply check if $f(x_1,y_1)$ and $f(x_2,y_2)$ have opposite signs (or one is zero). This condition can be expressed as: $$f(x_1,y_1)\cdot f(x_2,y_2)\leq 0$$