如何检查两条线段是否相交？

Question

我该如何检查两个线段是否相交呢？

我有以下数据：

Segment1 [ {x1,y1}, {x2,y2} ]
Segment2 [ {x1,y1}, {x2,y2} ] 

我需要用Python写一个小算法，来检测这两条线是否相交。

Answer 1

你不需要精确计算两个线段交叉的具体位置，只需要知道它们是否相交就可以了。这会让问题变得简单。

这个方法的思路是把一个线段当作“锚点”，然后把第二个线段分成两个点。
接下来，你需要找出这两个点相对于“锚点”线段的位置（在左边、在右边或共线）。
完成这一步后，检查一个点是否在左边，另一个点是否在右边（如果你想把共线的情况也算作交叉，可以包括共线的位置）。

然后，你需要交换锚点和分开的线段的角色，重复这个过程。

只有当一个点在左边，另一个点在右边时，才算有交叉。想了解更多详细的解释和每种可能情况的示例图，可以查看这个链接。

用这种方法实现会比直接找交点要简单得多，因为后者需要处理很多特殊情况。

更新

下面的函数可以帮助你理解这个思路（来源：《C语言中的计算几何》）。
备注：这个示例假设使用的是整数。如果你使用浮点数表示（这可能会让事情变得复杂），那么你需要确定一个小的值来表示“相等”（主要用于IsCollinear的判断）。

// points "a" and "b" forms the anchored segment.
// point "c" is the evaluated point
bool IsOnLeft(Point a, Point b, Point c)
{
     return Area2(a, b, c) > 0;
}

bool IsOnRight(Point a, Point b, Point c)
{
     return Area2(a, b, c) < 0;
}

bool IsCollinear(Point a, Point b, Point c)
{
     return Area2(a, b, c) == 0;
}

// calculates the triangle's size (formed by the "anchor" segment and additional point)
int Area2(Point a, Point b, Point c)
{
     return (b.X - a.X) * (c.Y - a.Y) -
            (c.X - a.X) * (b.Y - a.Y);
}

当然，在使用这些函数时，必须记得检查每个线段是否“在”另一个线段之间（因为这些是有限的线段，而不是无限的直线）。

此外，使用这些函数你可以判断你得到的是“正常”的交叉还是“非正常”的交叉。

• 正常交叉：没有共线的点。线段是“从一侧穿过另一侧”。
• 非正常交叉：一个线段只是“触碰”了另一个线段（至少有一个点是共线的）。

Answer 2

用户 @i_4_got 指向了 这个页面，里面有一个非常高效的 Python 解决方案。我在这里复制了一下，方便大家查看（因为如果我能在这里看到这个，我会很开心）：

def ccw(A,B,C):
    return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x)

# Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)

Answer 3

一条直线的方程是：

f(x) = A*x + b = y

对于一段线来说，情况是一样的，只不过x是在一个区间I内。

如果你有两段线，定义如下：

Segment1 = {(X1, Y1), (X2, Y2)}
Segment2 = {(X3, Y3), (X4, Y4)}

潜在交点的横坐标Xa（Xa,Ya）必须同时在区间I1和I2内，定义如下：

I1 = [min(X1,X2), max(X1,X2)]
I2 = [min(X3,X4), max(X3,X4)]

我们可以说Xa包含在：

Ia = [max( min(X1,X2), min(X3,X4) ),
      min( max(X1,X2), max(X3,X4) )]

现在，我们需要检查这个区间Ia是否存在：

if (max(X1,X2) < min(X3,X4)):
    return False  # There is no mutual abcisses

所以，我们有两个直线公式和一个共同的区间。你的直线公式是：

f1(x) = A1*x + b1 = y
f2(x) = A2*x + b2 = y

由于每段线有两个点，我们可以确定A1、A2、b1和b2：

A1 = (Y1-Y2)/(X1-X2)  # Pay attention to not dividing by zero
A2 = (Y3-Y4)/(X3-X4)  # Pay attention to not dividing by zero
b1 = Y1-A1*X1 = Y2-A1*X2
b2 = Y3-A2*X3 = Y4-A2*X4

如果这两段线是平行的，那么A1就等于A2：

if (A1 == A2):
    return False  # Parallel segments

一个点（Xa,Ya）如果在两条线上，必须同时满足两个公式f1和f2：

Ya = A1 * Xa + b1
Ya = A2 * Xa + b2
A1 * Xa + b1 = A2 * Xa + b2
Xa = (b2 - b1) / (A1 - A2)   # Once again, pay attention to not dividing by zero

最后一步是检查Xa是否包含在Ia内：

if ( (Xa < max( min(X1,X2), min(X3,X4) )) or
     (Xa > min( max(X1,X2), max(X3,X4) )) ):
    return False  # intersection is out of bound
else:
    return True

此外，你可以在开始时检查提供的四个点中是否有两个点不相等，以避免进行所有这些测试。