如何检查两个线段是否相交? [英] How can I check if two segments intersect?

问题描述

如何检查2个线段是否相交?

How can I check if 2 segments intersect?

我有以下数据:

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

我需要用Python编写一个小的算法来检测两行是否相交.

I need to write a small algorithm in Python to detect if the 2 lines are intersecting.

推荐答案

直线的等式是:

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

对于一个段，它完全相同，除了x包含在间隔I中.

For a segment, it is exactly the same, except that x is included on an interval I.

如果您有两个细分，则定义如下:

If you have two segments, defined as follow:

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

相交的潜在点(Xa，Ya)的绝对Xa必须包含在间隔I1和I2中，定义如下:

The abcisse Xa of the potential point of intersection (Xa,Ya) must be contained in both interval I1 and I2, defined as follow :

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

我们可以说Xa已包含在其中:

And we could say that Xa is included into :

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

现在，我们需要检查此间隔Ia是否存在:

Now, we need to check that this interval Ia exists :

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

因此，我们有两个直线公式，以及一个相互间隔.您的行公式为:

So, we have two line formula, and a mutual interval. Your line formulas are:

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

由于我们按段得到了两个点，因此我们能够确定A1，A2，b1和b2:

As we got two points by segment, we are able to determine A1, A2, b1 and 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 the segments are parallel, then A1 == A2 :

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

两条线上的点(Xa，Ya)必须验证公式f1和f2:

A point (Xa,Ya) standing on both line must verify both formulas f1 and 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中:

The last thing to do is check that Xa is included into 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

除此之外，您可以在启动时检查所提供的四个点中的两个点是否相等，以避免进行所有测试.

In addition to this, you may check at startup that two of the four provided points are not equals to avoid all that testing.

这篇关于如何检查两个线段是否相交?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！