I'm interested in dividing a square by a set of $M$ random straight lines. Every two lines are non-parallel. A straight line can intersect the square border only at integers positions (i.e. intersection occurs at 1, 2, 3, or N-1)
What is the fastest method to generate a set of $M$ random non-parallel straight lines inside $N \times N$ square?
For lines to be parallel, they need to have the same slope. Thus to make sure the lines are not parallel, all that needs to be compared is the slopes.
METHOD ONE
Also known as 'brute force'. Pick two random integers $a, b$ less than $N$ and greater than $0$. Then pick two random points $$(0, a),\ (0, b),\ (a, 0),\ (b, 0),\ (N, a),\ (N, b),\ (a, N),\ (b, N)$$ which are guaranteed to be integer points on the border of the square. Calculate the slope of the line connecting them and continue this process, making sure no two lines have the same slope, until $M$ lines have been created.
METHOD TWO
First, make a list of all possible slopes. For an $N \times N$ square, those will be $$0, \frac{1}{\pm N}, \frac{2}{\pm N}\cdots\frac{N - 2}{\pm N}, \frac{N - 1}{\pm N}, \pm1, \frac{\pm N}{N-1}, \frac{\pm N}{N-2}\cdots\frac{\pm N}{2}, \frac{\pm N}{1}, \infty$$ Then select $M$ unique slopes at random. For each slope $S$, pick a random integer $a$ from $0$ to $N$. If the slope is positive, use the points $(0, a)$ and $(a, 0)$ to construct two lines $y_1 = Sx + a$ and $y_2 = (S-a)x$. If the slope is negative, use the points $(0, a)$ and $(a, N)$ to construct two lines $y_1 = Sx + a$ and $y_2 = S(x - a) + N$. To make sure that the other point where the lines intersect the border of the square is an integer, use the following tests:
1. The line fails if $0\le y\le N$ and $y$ is not an integer at $x = N$ and $x = 0$
2. The line fails if $0\le x\le N$ and $x$ is not an integer at $y = N$ and $y = 0$
If the line fails, repeat the testing steps for a different value of $a$ until it does not fail.