Enumerating the "discrete straight lines" in an $n \times n$ grid.

Question

This question is related to this other question.

I would like to write an algorithm to enumerate all subsets of the $n^2$ squares of an $n \times n$ grid such that, for each subset, there exists a straight line crossing the inner region of all and only the squares of that subset. Inner region means that the line cannot cross just the border or the corner of the square.

Here you can find an interactive implementation of these "discrete straight lines".

The obvious algorithm that comes to mind is to take any two point on the outer border of the grid, draw a line passing through the two points and calculate all crossed squares. The problem is an actual algorithm can try only a finite number of couple of points. Therefore a side question could be how many points in the outer border must be considered, e.g. $2n$ for each side? And with what disposition?

Any other idea?

Answer 1

The square will be the set $[0,n]\times [0,n]$ in the plane. A lattice point is a point $P=(x,y)$ where $x,y\in \{0,1,\dots,n\}$. I will show how to generate all sets of squares cut by lines which do not pass through any lattice points.

Given two lattice points, $P_1$ and $P_2$, let $\ell(P_1,P_2)$ be the line which passes just below $P_1$, and which passes just above $P_2$. For this to be well-defined, we must additionally assume that the line segment $\overline{P_1P_2}$ hits no other lattice points. Equivalently, if $P_1=(x_1,y_1)$ and $P_2=(x_2,y_2)$, we require $\gcd(x_2-x_1,y_2-y_1)=1$.

Lemma: For every efficient line, $m$, there exist lattice points $P_1$ and $P_2$ such that $m$ cuts the exact same set of squares as $\ell(P_1,P_2)$.

Proof: Here is an algorithm to find $P_1$ and $P_2$, given $m$.

1. Translate $m$ upwards until just before it hits some lattice point. Call this point $P_1$.
2. Rotate $m$ clockwise about $P_1$ until just before you hit some other lattice point. Call this point $P_2$.
3. If $m$ is passing above $P_2$, then we have found the desired $(P_1,P_2)$. Otherwise, set $P_1$ to be the current value of $P_2$, and return to step $2$.

All that remains is to actually generate the set of squares cut by $\ell(P_1,P_2)$. The previous version of this algorithm had an algorithm which did not work, because I missed a lot of edge cases. I now have a working program, and I checked small cases by hand to see if it was generating the correct sets. However, it is a bit too complicated for me to fully describe in this answer.

• Python program: https://replit.com/@mearnest/Pixel-lines-in-n-x-n-grid
• Text file of cut sets, up to $n=15$. https://replit.com/@mearnest/Pixel-lines-in-n-x-n-grid#cut_sets.txt