1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Let us break the problem into some simpler sub-problems:

  1. Given a line and a square, determine if the line passes through the square.
  2. Assuming we know how to solve (1), find all squares from a finite tessellation through which the line passes.

To solve (2), we could iterate through all the squares and apply the solution to (1) to find the squares that are intersected by the line. Even better (more efficient), we could first find which of the four sides of the tessellation are crossed by the line, then find a border square on that side, and then check the neighboring squares. Once we find a neighboring square intersected by the line, check its neighbors that have not been checked yet, and continue until we find no more crossed squares.

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$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.