如何确定Z ^ 2中3个点是否完全共线

Question

另一个共线点问题.这个问题是,我正在使用整数运算,我正在寻找精确的共线性,而不是基于模糊epsilon的测试.

使用内联汇编,我可以得到一个确切的答案:x86乘法指令可以访问产品的高低部分,这两者在计算叉积(X - A)x(B - A)时都很重要; 我可以简单地将这两个部分组合在一起并测试为零.但是我希望有一种方法可以用C来做,那就是:

1. 防溢
2. 手提
3. 优雅

大致按此顺序.同时,这样做的方法是:不是:

1. 涉及铸造 double
2. 涉及使用更大的整数类型 - 假设我已经使用了可用于我的坐标组件类型的最大整数类型
3. 产生假阳性或假阴性.

关于X是否超出AB段,我不关心这个问题; 这只是四个无趣的比较.

我的噩梦是我必须将每个坐标组件分成两半,然后明确地进行长时间的乘法,这样我才能跟踪部分产品中的所有高半部分.(然后必须明确地使用add-with-carry.)

Answer 1

经过一些比较和简单的检查，您可以得到 2 个正数(x1,y1), (x2,y2)，您想要检查 是否x1*y2==x2*y1。

您可以使用欧几里德算法求出x1和的 GCD y1，然后将它们除以 GCM。为 做同样的事情(x2,y2)。如果在两种情况下得到相同的对，则两个向量具有相同的方向。