Total Number of Lines in a 2D Grid – Geometry Calculation

Question

I have a 2D grid of $M \times N$ points. I need to find the total number of lines (not line segments) passing through these points including the diagonals. For example:

• $M=2,N=2$: Number of lines $= 6$ (2 horizontal, 2 vertical, 2 diagonals)

• $M=2,N=3$: Number of lines $= 11$ (2 horizontal, 3 vertical, 6 diagonals)

• $M=3,N=3$: Number of lines $= 20$ (3 horizontal, 3 vertical, 14 diagonals)

• $M=2,N=4$: Number of lines $= 18$ (2 horizontal, 4 vertical, 12 diagonals)

• $M=3,N=4$: Number of lines $= 35$ (3 horizontal, 4 vertical, 28 diagonals)

Can someone help me in finding a general formula to find this?

Answer 1

The horizontal and vertical lines are straightforward. You get $M+N$ of those.

Let's take the lower left of the array at the origin so that the top row of points is at $y = M-1$ and the right column is at $x=N-1$.

Let's consider those diagonal lines that have positive slope, with one of the points being the origin.

We get a distinct diagonal for each pair $(x,y)$ for which $x$ and $y$ are relatively prime. (The line through $(0,0)$ and $(1,2)$ coincides with the one through $(0,0)$ and $(2,4)$.)

For counting the multiplicity, let's consider counting the lines with slope $2/3$ in a $9 \times 11$ grid.

If we start at the origin, this line goes through $(3,2)$. We can move along the $x$ axis until $(7,0)$, and after that we run out of points. We can go up a row, start at $(0,1)$ and go over again to $(7,1)$.

But if we go up to the next row, we can only go over to $(2,2)$ before we start running into points that we've drawn lines through.

However, we can continue to go up the left side. We only can go out to $x=2$ for the reason mentioned above. We can continue up to $(2,7)$, and that's the last new line for this slope.

So the formula for the number of lines with a rise of $m$ and a run of $n$ in an $M \times N$ grid is

$$L(M,N,m,n) = (m+1)(N-n) + (n+1)(M-m) - (m+1)(n+1) - 2.$$

Then, the total number of all lines (vertical, horizontal, positive slope, negative slope) is

$$T(M,N) = M + N + 2 \sum_{n=1}^{N-1} \sum_{m=1}^{M-1} L(M,N,m,n) C(m,n),$$

where $C(m,n) = 1$ if $m,n$ are coprime, and $0$ if they're not.