Let $a,b>0$ and suppose we have divided the domain $\Lambda:=[0,a]\times[0,b]$ into a grid of width $n_x$ and height $h_y$.

We enumerate the grid from bottom to top and left to right. Given $(x_0,y_0),(x,y)\in\Lambda$, I want to iterate over each grid cell through whose interior the line segment connecting $(x_0,y_0)$ and $(x,y)$ passes.

Suppose we number the first cell by $(0, 0)$ and the last cell by $(n_x-1,n_y-1)$. How can we find an efficient algorithm, which iterates over the desired cells?


1 Answer 1


Use a line drawing algorithm, such as Bresenham's.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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