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

Question

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

我有以下数据:

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

我需要在python中编写一个小算法来检测2条线是否相交.

更新:

Answer 1

User @ 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 2

一条线的等式是:

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

对于一个段,它是完全相同的,除了x包含在一个区间I.

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

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

潜在交点(Xa,Ya)的abcisse 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 3

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

我们的想法是将一个细分市场视为"锚点",并将第二个细分市场划分为2个点.
现在,您必须找到每个点到"锚定"段(OnLeft,OnRight或Collinear)的相对位置.
对两个点执行此操作后,检查其中一个点是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);
}

当然,在使用这些函数时,必须记住检查每个段是否位于另一个段之间(因为它们是有限段,而不是无限行).

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

• 正确:没有共线点.这些部分"从一侧到另一侧"相互交叉.
• 不正确:一个段仅"触及"另一个段(至少有一个点与锚定段共线).

Answer 4

假设两个段具有端点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 |

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

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

Answer 5

使用Shapely库使用以下intersects方法检查线段是否相交非常容易：

from shapely.geometry import LineString

line = LineString([(0, 0), (1, 1)])
other = LineString([(0, 1), (1, 0)])
print(line.intersects(other))
# True

line = LineString([(0, 0), (1, 1)])
other = LineString([(0, 1), (1, 2)])
print(line.intersects(other))
# False

Answer 6

这是我检查线路交叉以及交叉点发生位置的方法。让我们使用 x1 到 x4 和 y1 到 y4

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

然后我们需要一些向量来表示它们

dx1 = X2 - X1
dx2 = X4 - X3
dy1 = Y2 - Y1
dy2 = Y4 - Y3

现在我们看看行列式

det = dx1 * dy2 - dx2 * dy1

如果行列式为 0.0，则线段平行。这可能意味着它们重叠。如果它们仅在端点处重叠，则存在一种相交解。否则就会有无穷多个解。有了无限多个解决方案，你的交点是什么？所以这是一个有趣的特殊案例。如果您提前知道这些线不能重叠，那么您可以检查是否重叠，det == 0.0如果是，就说它们不相交并完成。否则，让我们继续

dx3 = X1 - X3
dy3 = Y1 - Y3

det1 = dx1 * dy3 - dx3 * dy1
det2 = dx2 * dy3 - dx3 * dy2

现在，如果 det、det1 和 det2 均为零，则您的线是共线的并且可能重叠。如果 det 为零，但 det1 或 det2 不为零，则它们不共线，而是平行，因此不存在交集。因此，如果 det 为零，那么现在剩下的就是一维问题而不是二维问题。我们需要检查两种方法之一，具体取决于 dx1 是否为零（这样我们可以避免被零除）。如果 dx1 为零，则只需对 y 值而不是下面的 x 执行相同的逻辑。

s = X3 / dx1
t = X4 / dx1

这会计算两个缩放器，这样，如果我们将向量 (dx1, dy1) 缩放 s，我们会得到点 (x3, y3)，而按 t 缩放，我们会得到 (x4, y4)。因此，如果 s 或 t 介于 0.0 和 1.0 之间，则点 3 或 4 位于我们的第一条线上。负值意味着该点位于向量的起点之后，而 > 1.0 则意味着该点位于向量的终点之前。0.0 表示它位于 (x1, y1)，1.0 表示它位于 (x2, y2)。如果 s 和 t 都 < 0.0 或都 > 1.0，则它们不相交。这可以处理平行线的特殊情况。

现在，如果det != 0.0那时

s = det1 / det
t = det2 / det
if s < 0.0 or s > 1.0 or t < 0.0 or t > 1.0:
    return false  # no intersect

这实际上与我们上面所做的类似。现在，如果我们通过了上述测试，那么我们的线段相交，我们可以很容易地计算交集，如下所示：

Ix = X1 + t * dx1
Iy = Y1 + t * dy1

如果您想更深入地了解数学的原理，请研究克莱默法则。

编辑：我已经修复了两个存在的错误，所以现在应该是正确的。我现在已经学会了足够的 python 来为此编写实际代码。尽管它确实正确处理了一些特殊情况，但除某些特殊情况外它仍然有效。特殊情况确实很难处理，我已经花了足够的时间在这上面并想继续前进。如果有人需要更好，那么他们至少有一个良好的起点来尝试和改进它。

import math

def line_intersection(line1, line2):
    x1, x2, x3, x4 = line1[0][0], line1[1][0], line2[0][0], line2[1][0]
    y1, y2, y3, y4 = line1[0][1], line1[1][1], line2[0][1], line2[1][1]

    dx1 = x2 - x1
    dx2 = x4 - x3
    dy1 = y2 - y1
    dy2 = y4 - y3
    dx3 = x1 - x3
    dy3 = y1 - y3

    det = dx1 * dy2 - dx2 * dy1
    det1 = dx1 * dy3 - dx3 * dy1
    det2 = dx2 * dy3 - dx3 * dy2

    if det == 0.0:  # lines are parallel
        if det1 != 0.0 or det2 != 0.0:  # lines are not co-linear
            return None  # so no solution

        if dx1:
            if x1 < x3 < x2 or x1 > x3 > x2:
                return math.inf  # infinitely many solutions
        else:
            if y1 < y3 < y2 or y1 > y3 > y2:
                return math.inf  # infinitely many solutions

        if line1[0] == line2[0] or line1[1] == line2[0]:
            return line2[0]
        elif line1[0] == line2[1] or line1[1] == line2[1]:
            return line2[1]

        return None  # no intersection

    s = det1 / det
    t = det2 / det

    if 0.0 < s < 1.0 and 0.0 < t < 1.0:
        return x1 + t * dx1, y1 + t * dy1

print("one intersection")
print(line_intersection(((0.0,0.0), (6.0,6.0)),((0.0,9.0), (9.0,0.0))))
print(line_intersection(((-2, -2), (2, 2)), ((2, -2), (-2, 2))))
print(line_intersection(((0.5, 0.5), (1.5, 0.5)), ((1.0, 0.0), (1.0, 2.0))))
print(line_intersection(((0, -1), (0, 0)), ((0, 0), (0, 1))))
print(line_intersection(((-1, 0), (0, 0)), ((0, 0), (1, 0))))

print()
print("no intersection")
print(line_intersection(((-1, -1), (0, 0)), ((2, -4), (2, 4))))
print(line_intersection(((0.0,0.0), (0.0,9.0)),((9.0,0.0), (9.0,99.0))))
print(line_intersection(((0, 0), (1, 1)), ((1, 0), (2, 1))))
print(line_intersection(((-1, 1), (0, 1)), ((0, 0), (1, 0))))
print(line_intersection(((1, -1), (1, 0)), ((0, 0), (0, -1))))

print()
print("infinite intersection")
print(line_intersection(((-1, -1), (1, 1)), ((0, 0), (2, 2))))
print(line_intersection(((-1, 0), (1, 0)), ((0, 0), (2, 0))))
print(line_intersection(((0, -1), (0, 1)), ((0, 0), (0, 2))))
print(line_intersection(((-1, 0), (0, 0)), ((0, 0), (-1, 0))))
print(line_intersection(((1, 0), (0, 0)), ((0, 0), (1, 0))))

Answer 7

这是使用点积的解决方案：

# assumes line segments are stored in the format [(x0,y0),(x1,y1)]
def intersects(s0,s1):
    dx0 = s0[1][0]-s0[0][0]
    dx1 = s1[1][0]-s1[0][0]
    dy0 = s0[1][1]-s0[0][1]
    dy1 = s1[1][1]-s1[0][1]
    p0 = dy1*(s1[1][0]-s0[0][0]) - dx1*(s1[1][1]-s0[0][1])
    p1 = dy1*(s1[1][0]-s0[1][0]) - dx1*(s1[1][1]-s0[1][1])
    p2 = dy0*(s0[1][0]-s1[0][0]) - dx0*(s0[1][1]-s1[0][1])
    p3 = dy0*(s0[1][0]-s1[1][0]) - dx0*(s0[1][1]-s1[1][1])
    return (p0*p1<=0) & (p2*p3<=0)

这是 Desmos 中的可视化：Line Segment Intersection

Answer 8

基于Liran和Grumdrig的优秀答案,这里有一个完整的Python代码来验证封闭的段是否相交.适用于共线段,平行于轴Y的段,退化段(详见恶魔).假设整数坐标.浮点坐标需要修改点相等性测试.

def side(a,b,c):
    """ Returns a position of the point c relative to the line going through a and b
        Points a, b are expected to be different
    """
    d = (c[1]-a[1])*(b[0]-a[0]) - (b[1]-a[1])*(c[0]-a[0])
    return 1 if d > 0 else (-1 if d < 0 else 0)

def is_point_in_closed_segment(a, b, c):
    """ Returns True if c is inside closed segment, False otherwise.
        a, b, c are expected to be collinear
    """
    if a[0] < b[0]:
        return a[0] <= c[0] and c[0] <= b[0]
    if b[0] < a[0]:
        return b[0] <= c[0] and c[0] <= a[0]

    if a[1] < b[1]:
        return a[1] <= c[1] and c[1] <= b[1]
    if b[1] < a[1]:
        return b[1] <= c[1] and c[1] <= a[1]

    return a[0] == c[0] and a[1] == c[1]

#
def closed_segment_intersect(a,b,c,d):
    """ Verifies if closed segments a, b, c, d do intersect.
    """
    if a == b:
        return a == c or a == d
    if c == d:
        return c == a or c == b

    s1 = side(a,b,c)
    s2 = side(a,b,d)

    # All points are collinear
    if s1 == 0 and s2 == 0:
        return \
            is_point_in_closed_segment(a, b, c) or is_point_in_closed_segment(a, b, d) or \
            is_point_in_closed_segment(c, d, a) or is_point_in_closed_segment(c, d, b)

    # No touching and on the same side
    if s1 and s1 == s2:
        return False

    s1 = side(c,d,a)
    s2 = side(c,d,b)

    # No touching and on the same side
    if s1 and s1 == s2:
        return False

    return True

Answer 9

这是另一个检查闭合线段是否相交的 python 代码。它是http://www.cdn.geeksforgeeks.org/check-if-two-given-line-segments-intersect/中 C++ 代码的重写版本。该实现涵盖了所有特殊情况（例如所有点共线）。

def on_segment(p, q, r):
    '''Given three colinear points p, q, r, the function checks if 
    point q lies on line segment "pr"
    '''
    if (q[0] <= max(p[0], r[0]) and q[0] >= min(p[0], r[0]) and
        q[1] <= max(p[1], r[1]) and q[1] >= min(p[1], r[1])):
        return True
    return False

def orientation(p, q, r):
    '''Find orientation of ordered triplet (p, q, r).
    The function returns following values
    0 --> p, q and r are colinear
    1 --> Clockwise
    2 --> Counterclockwise
    '''

    val = ((q[1] - p[1]) * (r[0] - q[0]) - 
            (q[0] - p[0]) * (r[1] - q[1]))
    if val == 0:
        return 0  # colinear
    elif val > 0:
        return 1   # clockwise
    else:
        return 2  # counter-clockwise

def do_intersect(p1, q1, p2, q2):
    '''Main function to check whether the closed line segments p1 - q1 and p2 
       - q2 intersect'''
    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)

    # General case
    if (o1 != o2 and o3 != o4):
        return True

    # Special Cases
    # p1, q1 and p2 are colinear and p2 lies on segment p1q1
    if (o1 == 0 and on_segment(p1, p2, q1)):
        return True

    # p1, q1 and p2 are colinear and q2 lies on segment p1q1
    if (o2 == 0 and on_segment(p1, q2, q1)):
        return True

    # p2, q2 and p1 are colinear and p1 lies on segment p2q2
    if (o3 == 0 and on_segment(p2, p1, q2)):
        return True

    # p2, q2 and q1 are colinear and q1 lies on segment p2q2
    if (o4 == 0 and on_segment(p2, q1, q2)):
        return True

    return False # Doesn't fall in any of the above cases

下面是一个测试函数来验证它是否有效。

import matplotlib.pyplot as plt

def test_intersect_func():
    p1 = (1, 1)
    q1 = (10, 1)
    p2 = (1, 2)
    q2 = (10, 2)
    fig, ax = plt.subplots()
    ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
    ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
    print(do_intersect(p1, q1, p2, q2))

    p1 = (10, 0)
    q1 = (0, 10)
    p2 = (0, 0)
    q2 = (10, 10)
    fig, ax = plt.subplots()
    ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
    ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
    print(do_intersect(p1, q1, p2, q2))

    p1 = (-5, -5)
    q1 = (0, 0)
    p2 = (1, 1)
    q2 = (10, 10)
    fig, ax = plt.subplots()
    ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
    ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
    print(do_intersect(p1, q1, p2, q2))

    p1 = (0, 0)
    q1 = (1, 1)
    p2 = (1, 1)
    q2 = (10, 10)
    fig, ax = plt.subplots()
    ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
    ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
    print(do_intersect(p1, q1, p2, q2))