java - 线段交点(交点)

Question

我创建了一个函数来计算两条线段的交点。

不幸的是，如果其中一个段是垂直的，下面的代码将不起作用

    public static Point intersection(Segment s1, Segment s2) {
    double x1 = s1.getP1().getX();
    double y1 = s1.getP1().getY() ;
    double x2 = s1.getP2().getX();
    double y2 = s1.getP2().getY() ;
    double x3 = s2.getP1().getX();
    double y3 = s2.getP1().getY();
    double x4 = s2.getP2().getX();
    double y4 = s2.getP2().getY();

    double d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
    if (d == 0) {
        return null;
    }
    double xi = ((x3 - x4) * (x1 * y2 - y1 * x2) - (x1 - x2) * (x3 * y4 - y3 * x4)) / d;
    double yi = ((y3 - y4) * (x1 * y2 - y1 * x2) - (y1 - y2) * (x3 * y4 - y3 * x4)) / d;
    Point p = new Point(xi, yi);
    if (xi < Math.min(x1, x2) || xi > Math.max(x1, x2)) {
        return null;
    }
    if (xi < Math.min(x3, x4) || xi > Math.max(x3, x4)) {
        return null;
    }
    return p;
}

当我有垂直线段时的问题，这个公式

double d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);

等于 0，该方法返回 null。

我该如何处理这个异常。

谢谢

Answer 1

无特殊情况的线相交

来自射影几何的背景，我会用齐次坐标写下这些点:

v1 = [x1, y1, 1]
v2 = [x2, y2, 1]
v3 = [x3, y3, 1]
v4 = [x4, y4, 1]

那么两点的连接线和两条线的交点都可以用叉积来表示:

[x5, y5, z5] = (v1 × v2) × (v3 × v4)

您可以对其进行去均质化以找到结果点

[x5/z5, y5/z5]

无需处理任何特殊情况。如果你的线是平行的，那么最后一个点将导致被零除，所以你可能想要捕捉这种情况。

对段的限制

不过，以上内容适用于无限行。您可能想保留返回 null 的代码如果交点落在边界框之外。但是，如果您想要真正的线段，则该代码是不正确的:您可能有一个交点，该交点位于其中一个线段之外，但仍在边界框内。

可以使用方向检查谓词来实现正确的检查。三个 vector 的行列式vi如果它们形成的三角形具有一个方向，则上面给出的符号将具有正号，而相反方向则具有负号。所以积分v3和v4躺在s1的不同侧面如果

det(v1, v2, v3) * det(v1, v2, v4) < 0

并以类似的方式v1和v2躺在s2的不同侧面如果

det(v3, v4, v1) * det(v3, v4, v2) < 0

因此，如果这两个条件都满足，则线段之间就有交集。如果要包含段端点，请更改 <到 ≤在这些不平等中。