c++ - 仅使用整数计算两条线的交点

Question

我可以很容易地计算出给定两条线的交点。如果我从两个顶点开始:

(x1,y1)
(x2,y2)

我可以通过执行 (y1-y2)/(x1-x2) 计算斜率，然后计算截距

y1 - 斜率 * x1

然后再做一次，所以我必须设置斜率和截距，然后就这样做:

x = (intercept2 - intercept1)/(slope1 - slope2)
y = slope1 * x + intercept1
(免责声明:这甚至可能行不通，但我已经得到了非常接近它的东西，它说明了我的一般技术)

BUT 仅适用于带小数或非整数的数据类型。假设顶点是:

(0,1)
(10,2)

计算斜率将得到 (1-2)/(0-10)，即 -1/-10 而不是 1/10，它是0。

如何获得仅使用整数产生有效结果的代码？

编辑:我根本不能使用 float !。没有类型转换，什么都没有。此外，值的上限为 65535。所有内容都是无符号的。

Answer 1

高中做分数减法时，老师教我们求公分母

所以 1/4 - 1/6 = 3/12 - 2/12 = 1/12

对你的斜坡做同样的事情。

int slope1 = n1 / d1;  // numerator / denominator
int slope2 = n2 / d2;
// All divisions below should have 0 for remainder
int g = gcd( d1, d2 ); // gcd( 4, 6 ) = 2
int d = d1 * d2 / g; // common denominator (12 above)
int n = (d/d1) * n1 - (d/d2) * n2; // (1 in 1/12 above)
// n1/d1 - n2/d2 == n/d

希望我做对了。