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

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 和y1 的GCD，然后将它们除以GCM。对 (x2,y2) 做同样的事情。如果您在两种情况下得到的是同一对，则两个 vector 的方向相同。