Line-grid intersection in 2D

Question

Say I have a line segment with known length L and a grid of pixels with dimension dX and dY along the X and Y axes. The line can begin from any arbitrary point within the grid and can have any arbitrary angle w.r.t the X and Y axes but its length is always the same (L). I would like to know what the maximum number of cells in the grid is that can be intersected with the line?

I was thinking something like this but am not sure:

ceil(L/dX) + ceil(L/dY) + 1

---

Numerical Simulations

In order to actually find what the correct answer is, I did a numerical simulation experiment where basically hundreds of millions of randomly generated lines with length L were started from a random point and fired randomly along various directions and the exact number of intersected grid pixels was counted to see what the max value is (since this was numerical simulations, I cannot say for sure that these values are correct):

1. L = 200, dX = 5, dY = 10 => Max no of intersected voxels = 47
2. L = 200, dX = 15, dY = 2 => Max no of intersected voxels = 103
3. L = 200, dX = 10, dY = 10 => Max no of intersected voxels = 31

Answer 1

If a line segment from one corner of a pixel to another corner has length less than $L$, we can move the endpoints a tiny bit to avoid ever intersecting a corner between pixels, and still have length less than $L$.

In this case, if the original corners were at horizontal distance $x \cdot dX$ and vertical distance $y \cdot dY$, the new segment will cross $x+1$ vertical cell boundaries and $y+1$ horizontal cell boundaries; since it will cross $x+y+2$ cell boundaries total, it will pass through $x+y+3$ cells.

So we want to maximize $x+y+3$ subject to $(x \cdot dX)^2 + (y \cdot dY)^2 < L^2$; the $<$ condition will usually not bother us, but it is there to make sure that a line segment beginning at a corner of a cell does not count as intersecting the cell.

If we forget about the integer constraint (that $x,y \in \mathbb Z$), then the method of Lagrange multipliers tells us that the maximum occurs close to the point where the ellipse $(x \cdot dX)^2 + (y \cdot dY)^2 = L^2$ has a tangent line with slope $-1$ (equal to the slope of $x+y+3=k$). This solution is $$ (x,y) = \left(\frac{dY}{dX} \cdot \frac{L}{\sqrt{dX^2 + dY^2}}, \frac{dX}{dY} \cdot \frac{L}{\sqrt{dX^2 + dY^2}}\right) $$ with $x+y+3 = L \sqrt{\frac1{dX^2} + \frac1{dY^2}} + 3$.

If we replace $x,y$ by $\lceil x\rceil - 1$ and $\lceil y \rceil-1$, we get an integer point where $(x \cdot dX)^2 + (y \cdot dY)^2 < L^2$, and the value $x+y+3$ decreases by at most $2$. (If it decreased by exactly $2$, then the original value $x+y+3$ was already unachievable, since it required having $(x \cdot dX)^2 + (y \cdot dY)^2 = L^2$ exactly.) Therefore this gives us the correct answer up to an error of $1$.

Unfortunately, fixing this error would require a search of integer points in some elliptical sliver of the form $(x \cdot dX)^2 + (y \cdot dY)^2 < L^2$ and $x+y \ge k$. Essentially, we are looking for fractional solutions that are worse than the optimal one but "round better". This is something that has to be done case-by-case.

But if you are okay with being off by $1$ sometimes, then we do have a closed-form solution: we get $$\left\lceil \frac{dY}{dX} \cdot \frac{L}{ \sqrt{dX^2+dY^2}}\right\rceil +\left\lceil \frac{dX}{dY} \cdot \frac{L}{ \sqrt{dX^2+dY^2}}\right\rceil +1$$ (or possibly $+2$) intersections.

Answer 2

Let us switch to polar coordinates.

$$x=L\cdot \cos(\phi)-x_1\\y=L\cdot\sin(\phi)-y_1$$ where $(x_0,y_0)$ is a known end-point and where: $$x_1 = \min(x_0,d_X-x_0)\\y_1 = \min(y_0,d_Y-y_0)$$

This corresponds to choosing the quandrant which points in direction closest to a corner.

We can now express the number as a function of $\phi\in[0,\pi/4]$: $$1+\left\lfloor\frac{x}{d_X}\right\rfloor+\left\lfloor\frac{ y}{d_Y}\right\rfloor=1+\left\lfloor\frac{L\cdot \cos(\phi)-x_1}{d_X}\right\rfloor+\left\lfloor\frac{L\cdot \sin(\phi)-y_1}{d_Y}\right\rfloor$$

More specifically, what we seek will be:

$$1+\max_{\phi}\left\{ \left\lfloor\frac{L\cdot \cos(\phi)-x_1}{d_X}\right\rfloor+\left\lfloor\frac{L\cdot \sin(\phi)-y_1}{d_Y}\right\rfloor \right\}$$

In most cases I suppose this will be related to the maximum Manhattan distance given a known Euclidean distance and a known distance between consecutive streets and avenues.

I think max shall be somehwere near $\phi \approx \arctan(d_Y/d_X)$.

In the special case if $d_X=d_Y$, then a tighter estimate shall be $\phi\approx$ 45 degrees and a factor $\sin(\pi/4)=\cos(\pi/4) = \frac{1}{\sqrt{2}}$ smaller than your estimate. There do as you mention exist isolated $\phi$ values for where the line passes precisely through integer coordinates on the lattice. But arbitrarily close to every such $\phi$ will be one with larger value.

But your estimate should work good enough as a not-as-tight upper bound.