如何检查两个线段是否相交？
我有以下数据：
Segment1 [ {x1,y1}, {x2,y2} ]
Segment2 [ {x1,y1}, {x2,y2} ]
我需要用Python编写一个小算法来检测这两条线是否相交。
26个回答
146
用户 @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)
- Grumdrig
3
16非常简洁优雅，但它不能很好地处理共线性问题，因此需要编写更多代码来解决这个问题。 - charles
15如果您需要处理共线性，可以查看http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect提供的解决方案。 - Zsolt Safrany
喜欢这个解决方案。非常简单和短小！我制作了一个wxPython程序，它可以画一条线并查看它是否与另一条线相交。我无法在此处放置它，因此它在此评论下方的某个位置。 - user1766438
93
一条直线的方程为：
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
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
除此之外，您可以在启动时检查四个提供的点中的两个是否不相等，以避免进行所有这些测试。
- OMG_peanuts
11
1片段，它们是片段，抱歉。麻烦您根据这些片段更新您的回答？ - aneuryzm
20这并不是很复杂，我写了许多（不必要的？）中间步骤来帮助理解。需要实现的主要步骤只有：检查相互区间的存在性，计算A1、A2、b1、b2和Xa，然后检查Xa是否包含在相互区间内。就这些 :) - OMG_peanuts
3A1和A2永远不会为零，因为如果在这种情况下A1 == A2的话，那么在此计算之前就已经返回了。 - inkredibl
4如果 A1 等于 A2，且 b1 等于 b2，则这些线段重叠在一起，并具有无限多个交点。 - lynxoid
6A1*x + b1 = y的公式不能处理垂直线，因此垂直线段应该使用这种方法单独处理。 - dmitri
显示剩余6条评论
42
您不必精确计算线段交点的位置，而只需了解它们是否相交。这将简化解决方案。
想法是将一个线段视为“锚点”，并将第二个线段分成2个点。
现在，您需要找到每个点与“锚”线段的相对位置（OnLeft、OnRight或Collinear）。
找到两个点的相对位置后，检查其中一个点是否为OnLeft，另一个是否为OnRight（或者如果您希望包括improper交叉点，则可以包括Collinear位置）。
然后，您必须以锚和分离线段的角色重复此过程。
当且仅当一个点为OnLeft，另一个点为OnRight时，才存在交点。请参见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);
}
当使用这些函数时，必须记得检查每个线段是否“位于”另一个线段之间（因为这些是有限线段，而不是无限线）。此外，使用这些函数，您可以了解您是否有一个“适当的”或“不适当的”交点。
- 适当的：没有共线点。线段从“侧面到侧面”相交。 - 不适当的：一个线段只“接触”另一个线段（至少有一个点与锚定线段共线）。
- Liran
4
基本上这也是我的想法。如果你只考虑点与点之间的相对位置，就可以决定它们的线段是否必须相交，而无需进行任何计算。 - Jochen Ritzel
@THC4k 嗯，实际上不太清楚。例如，请查看我添加到问题中的图像：2个点是“OnLeft”和“OnRight”，但2个线段并没有相交。 - aneuryzm
@Patrick，实际上不是这样的。根据哪个片段是“锚点”，在这种情况下两个点都可以是OnLeft或OnRight。（请参见我的更新答案）。 - Liran
1+1 我看过数十个解决此问题的答案，但这绝对是我见过的最清晰、最简单、最高效的。 :) - Miguel
17
假设两条线段的端点分别为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 |
计算两条线段的交点时，左侧每个行列式的符号必须与右侧相反，但是这两条线段之间不需要有任何关系。基本上，您要检查线段的每个点是否位于另一条线段定义的直线的相反侧。
- Victor Liu
3
它是否适用于不当的交叉点，即当交点位于一条线段上时？ - Sayam Qazi
@SayamQazi 如果您传递线段的端点，似乎会导致交叉失败。如果您在线段上：我认为它将是一个0与1/-1的比较，因此它将检测不到交叉点。 - Warty
1顺便解释一下：每个行列式都计算了两条线段向量端点的叉积。例如，左上角是CA x CB与右上角的DA x DB。这实际上测试了一个顶点在哪一侧（顺时针方向）。仍在尝试弄清楚它如何适用于不无限延伸的线段。 - Warty
17
使用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
- Georgy
2
是线还是线段？ - Dee
17
以下是使用点积的解决方案：
# 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上的可视化展示：线段相交。
- BenMan95
3
3喜欢你的解决方案，但如果两条线段在一条直线上，似乎会失败。 - H. Pope
这是两个叉积的点积。要排除线段端点，只需要重写返回值为(p0 * p1 < 0) & (p2 * p3 < 0)。 - Richard Z
1非常棒的解决方案@BenMan95。能否知道交点在哪里？ - Maxwell's Daemon
8
这是我检查线交叉和相交点的方法。我们将使用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
该计算产生两个标量，以便如果我们通过s缩放向量(dx1, dy1)，则得到点(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))))
- Jason Hoffoss
3
4笔误： "dx2 = X4 - X4" 应为 "dx2 = X4 - X3"。 - geowar
即使我纠正了dx2的拼写错误，它仍然无法工作... - WDUK
谢谢！这是我在“研究”中找到的最清晰的解释。 - Flex Elektro Deimling
7
基于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
- dmitri
2
“closed segments” 究竟是什么意思？ - Sam
@Sam 闭合线段包含其端点。例如，来自R的一组点的闭合线段将是[0,1]（0 <= x <= 1），而不是说]0,1]（0 < x <= 1）。 - dmitri
5
这里是另一个用Python编写的代码，用于检查闭合线段是否相交。它是C++代码http://www.cdn.geeksforgeeks.org/check-if-two-given-line-segments-intersect/的重写版本。此实现涵盖了所有特殊情况（例如，所有点共线）。
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))
- Fabian Ying
2
1测试代码中未定义
closed_segment_intersect()。 - hhquark1@hhquark 谢谢。我已经删除了这些行。我在测试时包含了这些行，以检查我的实现是否与另一个答案的实现一致（https://dev59.com/UW865IYBdhLWcg3wZNrT#18524383，我想是这个）。 - Fabian Ying
4
您有两条线段。用点A和点B定义一条线段，用点C和点D定义第二条线段。有一个巧妙的方法可以证明它们必须在线段范围内相交（请注意，这些线本身可能会在线段范围之外相交，因此您必须小心。好的代码也将监视平行线）。
这个技巧是测试点A和B必须位于线段CD的两侧，并且点C和D必须位于线段AB的两侧。
由于这是作业，我不会给您一个明确的解决方案。但是，用于查看点落在线的哪一侧的简单测试是使用点积。因此，对于给定的线CD，请计算该线的法向量（我将其称为N_C）。现在，只需测试这两个结果的符号即可。
如果这些结果的符号相反，则A和B是CD线的对侧。现在对另一条线AB进行相同的测试。它有法向量N_A。比较符号。
这个技巧是测试点A和B必须位于线段CD的两侧，并且点C和D必须位于线段AB的两侧。
由于这是作业，我不会给您一个明确的解决方案。但是，用于查看点落在线的哪一侧的简单测试是使用点积。因此，对于给定的线CD，请计算该线的法向量（我将其称为N_C）。现在，只需测试这两个结果的符号即可。
dot(A-C,N_C)
并且
dot(B-C,N_C)
如果这些结果的符号相反，则A和B是CD线的对侧。现在对另一条线AB进行相同的测试。它有法向量N_A。比较符号。
dot(C-A,N_A)
并且
dot(D-A,N_A)
我将让你自己想办法计算法向量。（在二维情况下，这很简单，但是你的代码会考虑A和B是否是不同的点吗？同样地，C和D是否也是不同的点？）
你仍然需要担心位于同一无限线上的线段，或者一个点实际上落在另一个线段上。良好的代码将应对每一个可能的问题。
- user85109
1
1“因为这是作业”是我见过的最愚蠢的不给出完整答案的理由。我来这里是为了获取实现交叉检测的最佳方法的想法，但现在我必须浪费时间去做一些额外的工作，因为显然这是某个地方的某个人的作业。 - Kröw
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接