线段相交(相交点) [英] Line Segments Intersection(intersection Point)

问题描述

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

I have created a function to calculate the intersection point of two line segment .

不幸的是，如果该段之一是verticale，下面的代码将无法工作

Unfortunantly the code below dosen't work if one of the segment is verticale

    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;
}

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

the problem when i have a vertical line segment , this formula

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

等于0，并且该方法返回null.

is equal to 0 and the method return null.

如何处理此异常.

谢谢

推荐答案

没有特殊情况的直线交点

从射影几何的背景出发，我将点写成齐次坐标:

Line intersection without special cases

Coming from a background of projective geometry, I'd write the points in homogeneous coordinates:

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

然后，可以使用叉积来表示连接两个点的线和两条线的交点:

Then both the line joining two points and the intersection of two lines can be expressed using the cross product:

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

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

which you can dehomogenize to find the resulting point as

[x5/z5, y5/z5]

无需处理任何特殊情况.如果您的线是平行的，那么最后一点将导致被零除，因此您可能想抓住这种情况.

without having to deal with any special cases. If your lines are parallel, the last point would lead to a division by zero, though, so you might want to catch that case.

不过，以上是针对无限行的.如果相交点超出边界框，则可能需要保留返回null的代码.但是，如果您想要真实的线段，那么该代码是不正确的:您可能有一个相交点位于线段之一之外，但仍在边界框之内.

The above is for infinite lines, though. You might want to keep the code which returns null if the point of intersection falls outside the bounding box. But if you want real segments, that code is incorrect: you could have a point of intersection which lies outside one of the segments but still inside the bounding box.

可以使用方向检查谓词来执行适当的检查.如果它们形成的三角形具有一个方向，则上面给出的三个矢量vi的行列式将具有正号，而相反方向的负号则由负号构成.因此，如果，v3和v4点位于s1的不同侧

A proper check can be implemented using an orientation-checking predicate. The determinant of three of the vectors vi given above will have positive sign if the triangle they form has one orientation, and negative sign for the opposite orientation. So the points v3 and v4 lie on different sides of s1 if

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

，并且类似的方式v1和v2位于s2的不同侧，如果

and in a similar way v1 and v2 lie on different sides of s2 if

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

因此，如果这两个条件都满足，则线段之间会有一个交集.如果要包括段端点，请在这些不等式中将<更改为≤.

so if both of these are satisfied, you have an intersection between the segments. If you want to include the segment endpoints, change the < to a ≤ in these inequalities.

这篇关于线段相交(相交点)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！