Search code examples
c++linetrace

Finding grid squares from a line

I'm trying to find a decent algorithm that allows me to find all the squares that a line intersects as it passes through a grid. Bresenham's algorithm does not work in my scenario because the endpoints of a line do not necessarily have to start or end in the center of a square. Even if it passes through a corner, a square will be counted.

Ive tried googling and I have not found many results.

enter image description here

Red is Bresenham's algorithm that does what I want it to do but it only works if the line endpoints start in the center of a square. Green is my ideal scenario.

Solution

  • Why not follow a 'numerical' sort of algorithm?
    Just evaluate a finitely large number of points in the line.
    From the coordinates of the point, it'd be easy to determine which square(s) they fall on.
    (You only have to add a new square to your list when the square the point lies in is different from the last point.)