1

我正在开发一个小游戏，它需要一个函数来计算两条线的交点。所以我从维基百科（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;

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

4

2 回答 2

3

该公式将输入数字之间的差异提高到三度，因此如果差异大约为三位数，您应该小心溢出一个int，它有九位数字，而且第一个数字可以上升到 2。一旦你溢出一个int，由于乘以正数，您开始看到负数，因此您的其余计算变得不正确。

要提高范围，请使用 64 位整数（即long long）作为中间结果。

于 2013-03-02T08:56:11.807 回答
0

不是 100% 确定，但你不能重新调整值吗？例如，除以最大的并使用浮动结果，您将拥有相同的大小，只是不同的比例。由于您不需要精确的交叉点，这应该可以工作，只记住平行线不会得到 0，因此您必须使用非常小的值 alpha 来定义范围 0 +/- alpha 来定义 D 值平行线。

于 2013-03-02T09:11:19.753 回答