Find the intersection between line and grid in a fast manner

Question

Is there anyway that allows me to find all the intersection points between a line and a grid? ( The intersection circles are not drawn to scale with each other, I know)

A brute force way is to compute very intersection for the x-y grid with the line, but this algorithm is awfully inefficient (O(m*n), where m is the number of x grid and n is the number of y grid).

I'm looking for a better algorithm on this.

Answer 1

Sounds like you need a Digital Differential Analyzer or Bresenham's line algorithm. Bresenham is the same algorithm used to draw lines on a bitmap; in this case, coloring a pixel is equivalent to checking for collisions in that square.