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

Question

如何检查2个线段是否相交？我有以下数据：Segment1 [ {x1,y1}, {x2,y2} ]Segment2 [ {x1,y1}, {x2,y2} ] 我需要在Python中编写一个小的算法来检测2行是否相交。

Answer 1

一条线的等式是：

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) )) ||

     (Xa > min( max(X1,X2), max(X3,X4) )) )

    return false; // intersection is out of bound

else

    return true;

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

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

您不必计算究竟哪里不段相交，但只有了解是否它们相交的。这将简化解决方案。

想法是将一个片段视为“锚点”，并将第二个片段分为2个点。

现在，您将必须找到每个点与“锚定”线段（OnLeft，OnRight或共线）的相对位置。

对两个点都这样做之后，请检查其中一个点是OnLeft，另一个是OnRight（或者，如果您还希望包括不正确的相交，则包括共线位置）。

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

仅当其中一个点为OnLeft而另一个为OnRight时，才存在交集。有关每种可能情况的示例图像，请参阅此链接以获取更详细的说明。

实现这种方法比实际实现找到相交点的方法要容易得多（考虑到很多拐角情况，您也必须处理）。

更新资料

以下函数应说明这一思想（来源：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);

}

当然，使用这些功能时，必须记住检查每个段是否位于另一个段“之间”（因为这些段是有限段，而不是无限行）。

此外，使用这些功能，您可以了解你是否已经有了一个正确或不正确的路口。

正确：没有共线点。这些段“从一侧到另一侧”彼此交叉。

不正确：一个线段仅“触摸”另一线段（至少一个点与锚定线段共线）。