2点を通る直線の整数表現（一意）

前提：直線は$ ax + by + c = 0という式で表せる。

2点$ (x_1, y_1), (x_2, y_2)が与えられたとき、これを通る直線を一意に表したい。

ただし、$ (x_1, y_1) \ne (x_2, y_2)とする。

$ x_1 = x_2のとき: $ x - x_1 = 0

$ x_1 \ne x_2のとき:

$ y = Ax + Bと表せる

$ A = \frac{y_1 - y_2}{x_1 - x_2}

$ B = y_1 - Ax_1

よって、$ y = \frac{y_1 - y_2}{x_1 - x_2} x + y_1 - \frac{y_1 - y_2}{x_1 - x_2} x_1

全体に$ x_1 - x_2をかけて、$ y(x_1 - x_2) = (y_1 - y_2)x + y_1(x_1 - x_2) - (y_1 - y_2) x_1

$ a = y_1 - y_2

$ b = x_2 - x_1

$ c = y_1(x_1 - x_2) - x_1(y_1 - y_2) = -a x_1 - b y_1

$ b > 0となるよう全体の符号を調整し、$ \gcd(a, b, c)で全体を割ればOK

まとめると、以下のとおりになる

code:rust

fn line<N: num_traits::PrimInt>((x1, y1): (N, N), (x2, y2): (N, N)) -> (N, N, N) {

if x1 == x2 {

(N::one(), N::zero(), -x1)

} else {

let mut a = y1 - y2;

let mut b = x2 - x1;

let mut c = -a * x1 - b * y1;

if b < N::zero() {

a = -a;

b = -b;

c = -c;

}

let g = num_integer::gcd(num_integer::gcd(a, b), c);

a /= g;

b /= g;

c /= g;

(a, b, c)

}