# Thread: Determine if Line passes through Squares

1. ## Determine if Line passes through Squares

Dear all, I'd like to know if there is a common approach to this problem:

I have a line segment defined by points a and b over a 2D plane. That plane is divided in Squares of the same size. I need to find a list of all the squares which the "ab" segment passes through.

I know:

• Points a and b coordinates
• The size and position of the Squares
• The Line Equation for ab (the Slope and the Y-Intercept)

I know I can pick any X value and calculate its Y intercept on the ab segment, and there for say if that point is inside a square or not, but this aproach may involve iterating and unwanted CPU computing (given I want to implement this concept into a computer graphics experiment).

Thanks in advance for any tip!!

2. ## Re: Determine if Line passes through Squares

Does any square in the plane have (0,0) as a vertex? Are points a and b both vertices of some squares in the plane? If the latter question is true then the former question is moot.

3. ## Re: Determine if Line passes through Squares

Originally Posted by Particlerama
Dear all, I'd like to know if there is a common approach to this problem:

I have a line segment defined by points a and b over a 2D plane. That plane is divided in Squares of the same size. I need to find a list of all the squares which the "ab" segment passes through.

I know:

• Points a and b coordinates
• The size and position of the Squares
• The Line Equation for ab (the Slope and the Y-Intercept)

I know I can pick any X value and calculate its Y intercept on the ab segment, and there for say if that point is inside a square or not, but this aproach may involve iterating and unwanted CPU computing (given I want to implement this concept into a computer graphics experiment).

Thanks in advance for any tip!!
From observation of your sketch ....

1. The line starts at the top left of the plane and ends at the bottom right of the plane
2. The first and last rows of the plane contain two adjacent squares where the line passes through. For the rows in-between, the line passes through three squares.
3. In your sketch, in the second row the adjacent boxes are 1 column to the right of the left edge of the plane. The third row is 3 columns over, the fourth is 5 columns over, the fifth is 7 and the sixth is 9. (Do you see the pattern?)
4. Given H and W of the plane, the slope of the line is H/W.
5. Given the size of the squares, the number of vertical squares is H/(Size) and the number of horizontal squares is W/(Size).

The above observations are all dependent on H and W. You need to create a set of simultaneous equations for the above observations where the solution to the equations identify the names of the squares that the line passes through.

Steve