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

How can I check if two segments intersect?

提问by aneuryzm

How can I check if 2 segments intersect?

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

I've the following data:

我有以下数据：

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

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

我需要在 Python 中编写一个小算法来检测 2 行是否相交。

采纳答案by OMG_peanuts

The equation of a line is:

直线方程为：

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

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

对于一个段，它完全一样，只是 x 包含在区间 I 中。

If you have two segments, defined as follow:

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

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

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

潜在交点 (Xa,Ya) 的横坐标 Xa 必须包含在区间 I1 和 I2 中，定义如下：

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

And we could say that Xa is included into :

我们可以说 Xa 包含在：

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

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

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

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

As we got two points by segment, we are able to determine A1, A2, b1 and b2:

当我们按段得到两个点时，我们可以确定 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

If the segments are parallel, then A1 == A2 :

如果这些段是平行的，则 A1 == A2 ：

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

A point (Xa,Ya) standing on both line must verify both formulas f1 and f2:

站在两条线上的点 (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

The last thing to do is check that Xa is included into Ia:

最后要做的是检查 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

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

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

回答by PierrOz

if your data define line you just have to prove that they are not parallel. To do this you can compute

如果您的数据定义了线，您只需要证明它们不平行。为此，您可以计算

alpha = float(y2 - y1) / (x2 - x1).

If this coefficient is equal for both Line1 and Line2, it means the line are parallel. If not, it means they will intersect.

如果该系数对于 Line1 和 Line2 都相等，则表示该线是平行的。如果不是，则意味着它们将相交。

If they are parallel you then have to prove that they are not the same. For that, you compute

如果它们是平行的，则您必须证明它们不相同。为此，你计算

beta = y1 - alpha*x1

If beta is the same for Line1 and Line2,it means you line intersect as they are equal

如果线 1 和线 2 的 beta 相同，则表示线相交，因为它们相等

If they are segment, you still have to compute alpha and beta as described above for each Line. Then you have to check that (beta1 - beta2) / (alpha1 - alpha2) is greater than Min(x1_line1, x2_line1) and less than Max(x1_line1, x2_line1)

如果它们是线段，您仍然需要按照上面对每条线的描述计算 alpha 和 beta。然后你必须检查 (beta1 - beta2) / (alpha1 - alpha2) 是否大于 Min(x1_line1, x2_line1) 并且小于 Max(x1_line1, x2_line1)

回答by kosii

Calculate the intersection point of the lines laying on your segments (it means basically to solve a linear equation system), then check whether is it between the starting and ending points of your segments.

计算放置在您的线段上的线的交点（基本上意味着解决线性方程组），然后检查它是否在您的线段的起点和终点之间。

回答by kosii

You have two line segments. Define one segment by endpoints A & B and the second segment by endpoints C & D. There is a nice trick to show that they must intersect, WITHIN the bounds of the segments. (Note that the lines themselves may intersect beyond the bounds of the segments, so you must be careful. Good code will also watch for parallel lines.)

你有两条线段。通过端点 A 和 B 定义一个段，通过端点 C 和 D 定义第二个段。有一个很好的技巧来表明它们必须在段的边界内相交。（请注意，线本身可能相交于线段的边界之外，因此您必须小心。好的代码也会注意平行线。）

The trick is to test that points A and B must line on opposite sides of line CD, AND that points C and D must lie on opposite sides of line AB.

诀窍是测试 A 点和 B 点必须在 CD 线的两侧，并且 C 和 D 点必须在 AB 线的两侧。

Since this is homework, I won't give you an explicit solution. But a simple test to see which side of a line a point falls on, is to use a dot product. Thus, for a given line CD, compute the normal vector to that line (I'll call it N_C.) Now, simply test the signs of these two results:

由于这是作业，我不会给你一个明确的解决方案。但是，查看点落在直线的哪一侧的简单测试是使用点积。因此，对于给定的线 CD，计算该线的法向量（我将其称为 N_C。）现在，只需测试这两个结果的符号：

dot(A-C,N_C)

and

和

dot(B-C,N_C)

If those results have opposite signs, then A and B are opposite sides of line CD. Now do the same test for the other line, AB. It has normal vector N_A. Compare the signs of

如果这些结果具有相反的符号，则 A 和 B 是线 CD 的两侧。现在对另一行 AB 进行相同的测试。它有法向量 N_A。比较标志

dot(C-A,N_A)

and

和

dot(D-A,N_A)

I'll leave it to you to figure out how to compute a normal vector. (In 2-d, that is trivial, but will your code worry about whether A and B are distinct points? Likewise, are C and D distinct?)

我会让你去弄清楚如何计算法向量。（在 2-d 中，这是微不足道的，但是您的代码会担心 A 和 B 是否是不同的点？同样，C 和 D 是否不同？）

You still need to worry about line segments that lie along the same infinite line, or if one point actually falls on the other line segment itself. Good code will cater to every possible problem.

您仍然需要担心位于同一条无限长线上的线段，或者一个点是否真的落在另一条线段本身上。好的代码将迎合所有可能的问题。

回答by Victor Liu

Suppose the two segments have endpoints A,B and C,D. The numerically robust way to determine intersection is to check the sign of the four determinants:

假设这两个段有端点 A、B 和 C、D。确定交集的数值稳健方法是检查四个行列式的符号：

| Ax-Cx  Bx-Cx |    | Ax-Dx  Bx-Dx |
| Ay-Cy  By-Cy |    | Ay-Dy  By-Dy |

| Cx-Ax  Dx-Ax |    | Cx-Bx  Dx-Bx |
| Cy-Ay  Dy-Ay |    | Cy-By  Dy-By |

For intersection, each determinant on the left must have the opposite sign of the one to the right, but there need not be any relationship between the two lines. You are basically checking each point of a segment against the other segment to make sure they lie on opposite sides of the line defined by the other segment.

对于相交，左侧的每个行列式必须与右侧的行列式符号相反，但两条线之间不必有任何关系。您基本上是根据另一个线段检查线段的每个点，以确保它们位于由其他线段定义的线的两侧。

See here: http://www.cs.cmu.edu/~quake/robust.html

见这里：http: //www.cs.cmu.edu/~quake/robust.html

回答by Liran

You don't have to compute exactly wheredoes the segments intersect, but only understand whetherthey intersect at all. This will simplify the solution.

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

The idea is to treat one segment as the "anchor" and separate the second segment into 2 points.
Now, you will have to find the relative position of each point to the "anchored" segment (OnLeft, OnRight or Collinear).
After doing so for both points, check that one of the points is OnLeft and the other is OnRight (or perhaps include Collinear position, if you wish to include improperintersections as well).

这个想法是将一个段视为“锚点”并将第二个段分成2个点。
现在，您必须找到每个点与“锚定”线段（OnLeft、OnRight 或 Colinear）的相对位置。
在对两个点都这样做之后，检查其中一个点是 OnLeft，另一个是 OnRight（或者可能包括共线位置，如果您还希望包括不正确的交叉点）。

You must then repeat the process with the roles of anchor and separated segments.

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

An intersection exists if, and only if, one of the points is OnLeft and the other is OnRight. See this linkfor a more detailed explanation with example images for each possible case.

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

Implementing such method will be much easier than actually implementing a method that finds the intersection point (given the many corner cases which you will have to handle as well).

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

Update

更新

The following functions should illustrate the idea (source: Computational Geometry in C).
Remark:This sample assumes the usage of integers. If you're using some floating-point representation instead (which could obviously complicate things), then you should determine some epsilon value to indicate "equality" (mostly for the IsCollinearevaluation).

以下函数应该说明这个想法（来源：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);
}

Of course, when using these functions, one must remember to check that each segment lies "between" the other segment (since these are finite segments, and not infinite lines).

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

Also, using these functions you can understand whether you've got a properor improperintersection.

此外，使用这些功能，您可以了解是否有正确或不正确的交叉点。

• Proper: There are no collinear points. The segments crosses each other "from side to side".
• Improper: One segment only "touches" the other (at least one of the points is collinear to the anchored segment).

• 正确：没有共线点。这些段“从一侧到另一侧”彼此交叉。
• 不正确：一个段仅“接触”另一个（至少一个点与锚定段共线）。

回答by Daniel

This is what I've got for AS3, don't know much about python but the concept is there

这就是我对 AS3 的了解，对 python 了解不多，但概念就在那里

    public function getIntersectingPointF($A:Point, $B:Point, $C:Point, $D:Point):Number {
        var A:Point = $A.clone();
        var B:Point = $B.clone();
        var C:Point = $C.clone();
        var D:Point = $D.clone();
        var f_ab:Number = (D.x - C.x) * (A.y - C.y) - (D.y - C.y) * (A.x - C.x);

        // are lines parallel
        if (f_ab == 0) { return Infinity };

        var f_cd:Number = (B.x - A.x) * (A.y - C.y) - (B.y - A.y) * (A.x - C.x);
        var f_d:Number = (D.y - C.y) * (B.x - A.x) - (D.x - C.x) * (B.y - A.y);
        var f1:Number = f_ab/f_d
        var f2:Number = f_cd / f_d
        if (f1 == Infinity || f1 <= 0 || f1 >= 1) { return Infinity };
        if (f2 == Infinity || f2 <= 0 || f2 >= 1) { return Infinity };
        return f1;
    }

    public function getIntersectingPoint($A:Point, $B:Point, $C:Point, $D:Point):Point
    {
        var f:Number = getIntersectingPointF($A, $B, $C, $D);
        if (f == Infinity || f <= 0 || f >= 1) { return null };

        var retPoint:Point = Point.interpolate($A, $B, 1 - f);
        return retPoint.clone();
    }

回答by Anonymous

for segments AB and CD, find the slope of CD

对于段 AB 和 CD，求 CD 的斜率

slope=(Dy-Cy)/(Dx-Cx)

extend CD over A and B, and take the distance to CD going straight up

将 CD 延伸到 A 和 B 上，然后将距离 CD 直线向上

dist1=slope*(Cx-Ax)+Ay-Cy
dist2=slope*(Dx-Ax)+Ay-Dy

check if they are on opposite sides

检查它们是否在相反的两侧

return dist1*dist2<0

回答by Grumdrig

User @i_4_got points to this pagewith a very efficent solution in Python. I reproduce it here for convenience (since it would have made me happy to have it here):

用户@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)

回答by Love Sharma

Resolved but still why not with python... :)

已解决，但为什么不使用 python... :)

def islineintersect(line1, line2):
    i1 = [min(line1[0][0], line1[1][0]), max(line1[0][0], line1[1][0])]
    i2 = [min(line2[0][0], line2[1][0]), max(line2[0][0], line2[1][0])]
    ia = [max(i1[0], i2[0]), min(i1[1], i2[1])]
    if max(line1[0][0], line1[1][0]) < min(line2[0][0], line2[1][0]):
        return False
    m1 = (line1[1][1] - line1[0][1]) * 1. / (line1[1][0] - line1[0][0]) * 1.
    m2 = (line2[1][1] - line2[0][1]) * 1. / (line2[1][0] - line2[0][0]) * 1.
    if m1 == m2:
        return False
    b1 = line1[0][1] - m1 * line1[0][0]
    b2 = line2[0][1] - m2 * line2[0][0]
    x1 = (b2 - b1) / (m1 - m2)
    if (x1 < max(i1[0], i2[0])) or (x1 > min(i1[1], i2[1])):
        return False
    return True

This:

这个：

print islineintersect([(15, 20), (100, 200)], [(210, 5), (23, 119)])

Output:

输出：

True

And this:

和这个：

print islineintersect([(15, 20), (100, 200)], [(-1, -5), (-5, -5)])

Output:

输出：

False