c++ - 维基百科的线交公式不能处理大数？

Question

我正在开发一个小游戏，它需要一个函数来计算两条线的交点。所以我从维基百科 (http://en.wikipedia.org/wiki/Line-line_intersection) 中获取了这个公式，并将其变成了一个函数。

bool lineline(int L1X1, int L1Y1, int L1X2, int L1Y2, int L2X1, int L2Y1, int L2X2, int L2Y2, int* X, int* Y) { // Returns the point of intersection of two lines
    int D = (L1X1 - L1X2) * (L2Y1 - L2Y2) - (L1Y1 - L1Y2) * (L2X1 - L2X2); // Denominator. If zero then no intersection

    if (D == 0) { // Parallel and possibly overlapping
        return false;
    } else {
        *X = ( (L1X1 * L1Y2 - L1Y1 * L1X2) * (L2X1 - L2X2) - (L1X1 - L1X2) * (L2X1 * L2Y2 - L2Y1 * L2X2) ) / D; // Calculate x
        *Y = ( (L1X1 * L1Y2 - L1Y1 * L1X2) * (L2Y1 - L2Y2) - (L1Y1 - L1Y2) * (L2X1 * L2Y2 - L2Y1 * L2X2) ) / D; // Calculate y

        std::cout << D << " | " << *X << " | " << *Y << "\n";

        if (*X >= Bmin(L1X1, L1X2) && *X <= Bmax(L1X1, L1X2) && *Y >= Bmin(L1Y1, L1Y2) && *Y <= Bmax(L1Y1, L1Y2)) {
            // Intersection is on first line
            if (*X >= Bmin(L2X1, L2X2) && *X <= Bmax(L2X1, L2X2) && *Y >= Bmin(L2Y1, L2Y2) && *Y <= Bmax(L2Y1, L2Y2)) {
                // Intersection is on second line
                return true;
            } else {
                // Intersection is on first, but not on second line
                return false;
            }
        } else {
            // Intersection is not on first line.
            return false;
        }

        return true;
    }
}

它工作得很好，例如当我用这些参数调用它时它返回 true

lineline(400, 0, 400, 2000, 0, 400, 2000, 400, &x, &y);

但是，当我将第二行向上移动 1300 个单位时...

lineline(400, 0, 400, 2000, 0, 1700, 2000, 1700, &x, &y) == false;

它返回错误。虽然第二个函数调用的两条线应该相交，对吧？它使用这些参数计算的值是:

D = -4000000
*X = 400;
*Y = -447;

谁能帮我解决这个问题？我已经坚持这一天了，我可能只是错过了一些简单的东西，就像上次一样，但我看不到它。提前致谢!

Answer 1

该公式将输入数字之间的差异提高到三次，因此如果差异大约为三位数，则应小心溢出具有九位数字的 int 加上第一位digit 最多可以达到 2。一旦 int 溢出，您就会开始看到负数是正数相乘的结果，因此您的其余计算将变得不正确。

要扩大范围，请使用 64 位整数(即 long long)作为中间结果。