Mapping line segments to $2$-dimensional area

Question

Given a $2$-dimensional space subdivided into $N\times N$ tiles, drawing a line from the edge's midpoint to the opposite field how can the $N$ tiles be found covering the majority of the line's path?

A visual aid:

Is there a better way to this than computing the linear equation and iteratively advancing in tiny steps to check which bucket we fall on? If not what is the lower limit step size to choose?

Answer 1

You are lucky. I've spent weeks coming out with an algorithm for solving this type of problem. Here is how you should approach it:

1. Notice that you have a regular grid in both $x$ and $y$ directions. In your particular drawings you have vertical planes at $x_j=2j+1$, with $j\in\mathbb Z$, or more exactly in a subset of that, from $j_{min}$ to $j_{max}$. Similarly, your horizontal planes have $y_k=2k+1$.
2. Calculate the intersections of the lines with your horizontal and vertical planes. Use $$\tan \theta=\frac yx$$ That means that the intersections with vertical planes occur at $(x_j,x_j\tan\theta)$, and the intersections with vertical planes are at $(y_k\cot \theta,y_k)$. Choose only the ones that occur inside (or on the border) of your tiles.
3. If $|\tan\theta|<1$, then your line is mostly horizontal. Then sort your intersections by the $x$ coordinate, and calculate the length along $x$ between your intersections. Choose the largest $N$ of those, and these are where your length is longest. If $|\tan\theta|>1$, just use the $y$ lengths instead.
4. Once you have the $x$ boundaries of any interval, choose the midpoint, calculate the $y$ position (from the tangent formula), then figure out in which $y$ interval it lands. Similarly, just switch $y$ and $x$ if you calculated the $y$ intervals.