如何在Java中找到两条线段是否相交的算法？

Question

我需要实现一个名为disjointSegments的方法，如果线段不相交，则返回true，否则返回false

这就是我现在所拥有的。应该有两段，ab和cd

public static boolean disjointSegments(Point2D.Double a, Point2D.Double b,
        Point2D.Double c, Point2D.Double d)

这是一个赋值，它说我可以用delta方法计算出来，这是一种计算矩阵行列式的方法

我已经实现了delta方法

public static double delta(Point2D.Double a, Point2D.Double b,
        Point2D.Double c) {
    return (a.getX() * b.getY() * 1) + ( a.getY() * 1 * c.getX()) + (1 * b.getX() * c.getY()) - (1 * b.getY() * c.getX())
            - (a.getX() * 1 * c.getY()) - (a.getX() * b.getY() * 1);
}

那么我怎么才能知道线段是否不相交呢

Answer 1

函数delta是cross product的一个实现。这可用于确定点或向量之间是顺时针还是逆时针。如果ab x cd > 0，两个向量为顺时针方向；如果ab x cd < 0，两个向量为逆时针方向；如果ab x cd = 0，两个向量为共线方向

要使用此选项确定两个向量相交，可以执行以下操作：

假设您有4个点：a、b、c、d。然后您需要进行4次计算：

(a - c) x (d - c) < 0
(b - c) x (d - c) > 0

通过这两个计算，您可以确定点a是否为逆时针方向，点b是否为顺时针方向（反之亦然）到向量cd。如果这一点成立，那么这些点位于向量的不同边上，这就是它们之间需要相交的地方。现在，您必须测试d和c是否存在相同的问题

(d - a) x (b - a) < 0
(c - a) x (b - a) > 0

如果这也保持两个向量相交

编辑：如果本例中的所有4个计算均为真，则存在向量的交点。对于问题中的不相交示例，这是正确的，其中没有点与向量共线。如果您还必须测试这一点，则有必要进行共线测试

术语a - c由两点构成向量

a - c => ac.x = a.x - c.x, ac.y = a.y - c.y

Answer 2

由于您只需要2D空间中的真/假结果，因此有一种有效的方法来计算：

bool segmentsIntersect(Point2D a, Point2D b, Point2D c, Point2D d) {
    float det = (b.x - a.x) * (d.y - c.y) - (d.x - c.x) * (b.y - a.y);
    if (det == 0)
        return false; //Lines are parallel
    float lambda = ((d.y - c.y) * (d.x - a.x) + (c.x - d.x) * (d.y - a.y)) / det;
    float gamma = ((a.y - b.y) * (d.x - a.x) + (b.x - a.x) * (d.y - a.y)) / det;
    return (0 < lambda && lambda < 1) && (0 < gamma && gamma < 1);
}

Answer 3

这里有一个针对一般情况的解决方案。特殊情况见this-page 9

public static int orientation(Point p, Point q, Point r) {
    double val = (q.getY() - p.getY()) * (r.getX() - q.getX())
            - (q.getX() - p.getX()) * (r.getY() - q.getY());

    if (val == 0.0)
        return 0; // colinear
    return (val > 0) ? 1 : 2; // clock or counterclock wise
}

public static boolean intersect(Point p1, Point q1, Point p2, Point q2) {

    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);

    if (o1 != o2 && o3 != o4)
        return true;

    return false;
}

public static void main(String[] args) {
    Point p1 = new Point(1,1);
    Point q1 = new Point(2,0);
    Point p2 = new Point(1,0);      
    Point q2 = new Point(3,2);      
    System.out.println("intersect: "+intersect(p1, q1, p2, q2));
}

答复: 交集：对