precision - 平面上两个三角形的交点

Question

两个三角形的交点要么是空的，要么是 n 边形（n 最多为 6）。

理论上，很容易想出一个算法来计算交叉区域。可以计算所有线段的可能交点，并将它们与三角形角点的点结合起来。

在实践中，存在一些数字问题。如果线段（几乎）平行，它们可能有也可能没有交点，并且其计算可能不精确（通常除以矩阵的行列式，然后近似为零）。

有什么建议可以避免这些数值不稳定性吗？

Answer 1

我不知道如何找到相交区域，但是如果您只想知道它们是否相交，那么Olivier Devlers 和 Philippe Guigue 的文章“Faster Triangle-Triangle Intersection Tests”中的算法应该非常稳定根据一些多项式顺序理论，我不太了解，也没有在参考资料中查找。

遵循我自己的 JavaScript 实现。我不能保证它是正确的，因为它没有看到足够的现实世界行动。

function det3(a, b, c)
{
    var a11 = a[0] - c[0]; var a12 = a[1] - c[1];
    var a21 = b[0] - c[0]; var a22 = b[1] - c[1];

    return a11 * a22 - a21 * a12;
}

function planar_intersect(vs, t1, t2)
{
    var p1, q1, r1;
    var p2, q2, r2;

    // I am doing this weird unpacking of the vertices because
    // originally they were on R³, and I had a code here to project
    // them to some orthogonal plane on R².
    p1 = t1.a; q1 = t1.b; r1 = t1.c;
    p2 = t2.a; q2 = t2.b; r2 = t2.c;

    // Ensure both triangles are counterclockwise
    var tmp;
    if(det3(p1, q1, r1) < 0) {
        tmp = q1;
        q1 = r1;
        r1 = tmp;
    }
    if(det3(p2, q2, r2) < 0) {
        tmp = q2;
        q2 = r2;
        r2 = tmp;
    }

    // Calculate signed areas of triangles
    var s1 = Array(3);

    // If 0, the vertex is on the edge of the other triangle
    s1[0] = det3(p1, p2, q2);
    if(s1[0] == 0)
        return true;

    s1[1] = det3(p1, q2, r2);
    if(s1[1] == 0)
        return true;

    s1[2] = det3(p1, r2, p2);
    if(s1[2] == 0)
        return true;

    // If all positive, the vertex is internal to the other triangle
    if(s1[0] > 0 && s1[1] > 0 && s1[2] > 0) {
        return true;
    }

    // Reorder t2 in order for a1 to be in the right area
    for(var i = 0; i < 2; ++i) {
        if(s1[0] > 0 && s1[2] <= 0) {
            break;
        }

        tmp = s1[0];
        s1[0] = s1[1];
        s1[1] = s1[2];
        s1[2] = tmp;

        tmp = p2;
        p2 = q2;
        q2 = r2;
        r2 = tmp;
    }

    if(s1[1] > 0) {
        // Follow Figure 9 tree.
        if(det3(r2, p2, q1) >= 0) {
            // II.a
            if(det3(r2, p1, q1) >= 0) {
                // III.a
                if(det3(p1, p2, q1) >= 0) {
                    return true;
                } else {
                    // IV.a
                    if(det3(p1, p2, r1) >= 0) {
                        // V
                        return det3(q1, r1, p2) >= 0;
                    } else {
                        return false;
                    }
                }
            } else {
                return false;
            }
        } else {
            // II.b
            if(det3(r2, p2, r1) >= 0) {
                // III.b
                if(det3(q1, r1, r2) >= 0) {
                    // IV.b
                    return det3(p1, p2, r1) <= 0;
                } else {
                    return false;
                }
            } else {
                return false;
            }
        }
    } else {
        // Follow Figure 10 tree.
        if(det3(r2, p2, q1) >= 0) {
            // II.a
            if(det3(q2, r2, q1) >= 0) {
                // III.a
                if(det3(p1, p2, q1) >= 0) {
                    // IV.a
                    return det3(p1, q2, q1) <= 0;
                } else {
                    // IV.b
                    if(det3(p1, p2, r1) >= 0) {
                        // V.a
                        return det3(r2, p2, r1) >= 0;
                    } else {
                        return false;
                    }
                }
            } else {
                // III.b
                if(det3(p1, q2, q1) <= 0) {
                    // IV.c
                    if(det3(q2, r2, r1) >= 0) {
                        // V.b
                        return det3(q1, r1, q2) >= 0;
                    } else {
                        return false;
                    }
                } else {
                    return false;
                }
            }
        } else {
            // II.b
            if(det3(r2, p2, r1) >= 0) {
                // III.c
                if(det3(q1, r1, r2) >= 0) {
                    // IV.d
                    return det3(r1, p1, p2) >= 0;
                } else {
                    // IV.c
                    if(det3(q1, r1, q2) >= 0) {
                        // V.c
                        return det3(q2, r2, r1) >= 0;
                    } else {
                        return false;
                    }
                }
            } else {
                return false;
            }
        }
    }
}