# Computing the number of squares which are intersected by a line internally

There's a line from (x1,y1) to (x2,y2) in a grid of squares of unit length. Write a program to compute the number of squares which are intersected by the line internally, i.e squares which are only touched by the line should not be counted. Notes x1,y1,x2,y2 are all integers. 0 <= x1,y1,x2,y2 <= 10000 Write the program so that it accepts 4 command line parameters - x1,y1,x2,y2 The output of the program should be a single line consisting of only the integer output Example: Input (x1 y1 x2 y2): 1 1 6 6 Output (No. of squares): 5

please help me to understand how these squares will generate? do i need to predefined all the squares in a 2d matrix form?

• do you remember from back in grade school how to calculate the slope of a line, given its' two end points? We are unlikely to do your homework for you; however, if you make some effort, and post the results of your effort, we would be glad to help you with any problems with your code. – user3629249 Jul 18 '15 at 21:17
• Welcome to Computer Science Stack Exchange. I think you may have an error in your text: It should probably be: "i.e squares which are only touched by the line should not be counted.". You should draw pictures to understand what happens. Make several simple ones, varying the orientation of the line, But you need not draw them with the computer. Hint: an important issue in this problem is to compute the GCD of $x_1-x_2$ and $y_1-y_2$. – babou Jul 18 '15 at 22:05
• Hint: Bresenham's algorithm. – David Richerby Jul 18 '15 at 22:38
• thank's a lot sir, for the suggestion and the corrections. – Abhishek Karmakar Jul 19 '15 at 17:40

## 1 Answer

As the question says, the program should be as follows:

### INPUT:

4 integer numbers: $(x_1,y_1)$, $(x_2,y_2)$

### OUTPUT:

a single number $n$.

$n$ should be the number of squares that are touched by a line that starts at $(x_1,y_1)$ and ends at $(x_2,y_2)$. Assuming the squares are of length 1, and the first square has corners at (0,0), (1,0), (0,1), (1,1).

That's it. Nobody gives you the squares as a matrix or any other form. They are not in the memory, and nobody tells you how to construct them. Furthermore, your program DOES NOT NEED to construct the squares. It can, but it needs not. The output $n$ can be found in a purely mathematical way.

• PS, an easy counting method, is to start from $y_1$ and check when the line crosses horizontal lines (e.g, the lines $y=1,y=2,y=3$, etc.), for each gap of $\Delta y=1$ check the shift in the $x$ value - it is exactly the number of squares between these two horizontal lines (when rounded). The $x$ shift can be computed,e.g., by the slope of the input line. – Ran G. Jul 18 '15 at 22:52