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

Question

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

我有以下数据：

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

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

Answer 1

用户@i4u使用Python中非常有效的解决方案获得了指向this page的点。我在这里复制它是为了方便（因为它会让我很高兴有它在这里）：

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 2

直线的方程式是：

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

对于一个段，它是完全相同的，只是x包含在一个区间I上

如果有两个段，定义如下：

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

潜在交点（Xa，Ya）的方位角Xa必须包含在区间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

除此之外，您可以在启动时检查所提供的四个点中的两个不等于，以避免所有的测试。

Answer 3

您不必精确计算线段在何处相交，而只需了解它们是否相交。这将简化解决方案。

我们的想法是将一段视为“锚”，并将第二段分为2个点。
现在，您必须找到每个点与“锚定”线段（OnLeft、OnRight或Collinear）的相对位置。
对这两个点执行此操作后，请检查其中一个点是OnLeft，另一个是on right（或者，如果希望包括不正确的交点，也可以包括共线位置）。

然后，必须使用锚定和分离段的角色重复该过程。

如果且仅当其中一个点位于左，而另一个点位于右，则存在交集。请参阅this link以获取有关每个可能情况的示例图像的更详细解释。

实现这样的方法要比实际实现一个找到交叉点的方法容易得多（考虑到您还必须处理的许多角点情况）。

更新

下面的函数应该说明这个想法（源代码：Computational Geometry in C）。
备注：此示例假定使用整数。如果您使用一些浮点表示（这显然会使事情复杂化），那么您应该确定一些epsilon值来表示“相等”（主要用于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);
}

当然，在使用这些函数时，必须记住检查每一段是否位于另一段之间（因为这是有限段，而不是无限线）。

此外，使用这些函数可以了解是否有正确的或不正确的交集。

• 正确：没有共线点。各部分交叉 其他“从一边到另一边”。
• 不正确：一个段只“接触”另一个段（至少一个 这些点与 锚定段）。