如何检查两个线段是否相交的Python方法
考虑以下交叉线的例子：
l1 = ((20,5),(40,20))
l2 = ((20,20),(40,5))
l3 = ((30,30),(30,5)) # vertical line
我写了下面的代码来计算交叉点的x和y坐标（具体理论细节请参考）
def gradient(l):
"""Returns gradient 'm' of a line"""
m = None
# Ensure that the line is not vertical
if l[0][0] != l[1][0]:
m = (1./(l[0][0]-l[1][0]))*(l[0][1] - l[1][1])
return m
def parallel(l1,l2):
if gradient(l1) != gradient(l2):
return False
return True
def intersect(l):
"""Returns intersect (b) of a line using the equation of
a line in slope and intercepet form (y = mx+b)"""
return l[0][1] - (gradient(l)*l[0][0])
def line_intersection(l1,l2):
"""Returns the intersection point (x,y) of two line segments. Returns False
for parallel lines"""
# Not parallel
if not parallel(l1,l2):
if gradient(l1) is not None and gradient(l2) is not None:
x = (1./(gradient(l1) - gradient(l2))) * (intersect(l2) - intersect(l1))
y = (gradient(l1)*x) + intersect(l1)
else:
if gradient(l1) is None:
x = l1[0][0]
y = (gradient(l2)*x) + intersect(l2)
elif gradient(l2) is None:
x = l2[0][0]
y = (gradient(l1)*x) + intersect(l1)
return (x,y)
else:
return False
示例会话：
>>> line_intersection(l1,l2)
(30.0, 12.5)
>>> line_intersection(l2,l3)
(30, 12.5)
我希望在处理有限长度的线段时，能更高效地改进我的代码，因为它们可能实际上并不会相交。
l1 = ((4,4),(10,10))
l2 = ((11,5),(5,11))
l3 = ((11,5),(9,7))
line_intersection(l1,l2) #valid
(8.0, 8.0)
line_intersection(l1,l3) # they don't cross each other
(8.0, 8.0)
line_intersection(l2,l3) #line parallel
False
我现在的不太优雅的解决方案如下。
def crosses(l1,l2):
if not parallel(l1,l2):
x = line_intersection(l1,l2)[0]
xranges = [max(min(l1[0][0],l1[1][0]),min(l2[0][0],l2[1][0])),min(max(l1[0][0],l1[1][0]),max(l2[0][0],l2[1][0]))]
if min(xranges) <= x <= max(xranges):
return True
else:
return False
else:
return False
crosses(l1,l2)
True
crosses(l2,l3)
False
我在寻找是否有可能改进我在Python中的函数风格。
1 个回答
在我看来，任何能返回正确答案的代码都很棒，做得好。
这里有一些建议：
def parallel(l1,l2):
if gradient(l1) != gradient(l2):
return False
return True
可以写成
def parallel(l1,l2):
return gradient(l1) == gradient(l2)
同样，
if min(xranges) <= x <= max(xranges):
return True
else:
return False
可以写成
return min(xranges) <= x <= max(xranges)
尽量避免使用整数索引，尤其是像 l1[0][0] 这样的双层整数索引。
用单词或变量名比用数字索引更容易阅读和理解。
解决整数索引的一种方法是使用“元组解包”：
(x1, y1), (x2, y2) = l1
这样 l1[0][0] 就变成了 x1。这可以提高你在 gradient 和 crosses 函数中的代码可读性。
有两种情况会导致直线平行。如果直线不共线，那么它们永远不会相交。但如果直线共线，它们会在每个点相交。
说
line_intersection(line, line)
在直线共线时是 False 似乎不太准确。如果这条直线恰好是同一条线，那就更不对了 :)
我建议如果直线共线，返回一个任意的交点；如果直线平行但不共线，则返回 None。
在比较浮点数是否相等时可能会出现一个bug：
In [81]: 1.2 - 1.0 == 0.2
Out[81]: False
这不是Python的bug，而是由于浮点数的内部表示造成的问题，影响到任何语言中的浮点计算。它可能会在任何尝试比较浮点数是否相等的代码中引入bug，比如这里：
def parallel(l1,l2):
if gradient(l1) == gradient(l2): ...
所以，与其比较浮点数是否相等，我们最好测试两个浮点数是否在某个容忍范围内接近。例如，
def near(a, b, rtol=1e-5, atol=1e-8):
# Essentially borrowed from NumPy
return abs(a - b) < (atol + rtol * abs(b))
def parallel(l1,l2):
if near(gradient(l1), gradient(l2)): ...
PEP8风格指南说：
绝不要使用字符 'l'（小写字母l）、'O'（大写字母O）或 'I'（大写字母I）作为单字符变量名。
在某些字体中，这些字符与数字1和0是无法区分的。
所以我建议用 line1 代替 l1。
现在，正如@george指出的，代码中有很多地方将垂直线作为特例处理（if gradient is None）。如果我们使用直线的参数形式，就可以以相同的方式处理所有直线。这样代码会更简单，因为数学会更简单。
如果你知道直线上的两个点 (x1, y1) 和 (x2, y2)，那么直线的参数形式是
l(t) = (x1, y1)*(1-t) + (x2, y2)*t
其中 t 是一个标量。随着 t 的变化，你会得到直线上的不同点。注意参数形式的一些相关事实：
当
t = 1时，右侧的第一个项消失，所以你得到(x2, y2)。当
t = 0时，右侧的第二个项消失，所以你得到(x1, y1)*(1-0) = (x1, y1)。方程的右侧线性依赖于
t。没有t**2项或其他非线性依赖于t的项。所以参数形式描述的是一条直线。
为什么直线的参数形式很强大？
线段 (x1, y1) 到 (x2, y2) 内的点对应于
t值在0到1之间（包括0和1）。所有其他的t值对应于线段外的点。注意，垂直线在参数形式中并没有什么特别之处。你不必担心无限斜率。每条直线都可以以相同的方式处理。
我们如何利用这个事实？
如果我们有两条直线的参数形式：
l1(t) = (x1, y1)*(1-t) + (x2, y2)*t
l2(s) = (u1, v1)*(1-s) + (u2, v2)*s
（想象 x1, y1, x2, y2, u1, v1, u2, v2 是给定的常数），那么当
l1(t) = l2(s)
时，直线相交。
现在，l1(t) 是一个二维点。l1(t) = l2(s) 是一个二维方程。方程中包含了 x 坐标和 y 坐标的方程。所以我们实际上有两个方程和两个未知数（t 和 s）。我们可以求解这些方程来找到 t 和 s！(希望如此。如果直线不相交，那么就没有 t 和 s 的解。）
那么我们来做一些数学运算吧 :)
l1(t) = (x1, y1) + (x2-x1, y2-y1)*t
l2(s) = (u1, v1) + (u2-u1, v2-v1)*s
l1(t) = l2(s) 意味着两个标量方程：
x1 + (x2-x1)*t = u1 + (u2-u1)*s
y1 + (y2-y1)*t = v1 + (v2-v1)*s
(x2-x1)*t - (u2-u1)*s = u1-x1
(y2-y1)*t - (v2-v1)*s = v1-y1
我们可以将其重写为矩阵方程：
使用 克拉默法则，我们可以求解 t 和 s：如果
那么
注意，从数学角度来看，克拉默法则是有效的（而且容易编码），但它的 数值特性较差（也可以参考 GEPP与克拉默法则）。对于严肃的应用，使用 LU分解 或 LAPACK（通过NumPy可用）。
所以我们可以这样编码：
def line_intersection(line1, line2):
"""
Return the coordinates of a point of intersection given two lines.
Return None if the lines are parallel, but non-collinear.
Return an arbitrary point of intersection if the lines are collinear.
Parameters:
line1 and line2: lines given by 2 points (a 2-tuple of (x,y)-coords).
"""
(x1,y1), (x2,y2) = line1
(u1,v1), (u2,v2) = line2
(a,b), (c,d) = (x2-x1, u1-u2), (y2-y1, v1-v2)
e, f = u1-x1, v1-y1
# Solve ((a,b), (c,d)) * (t,s) = (e,f)
denom = float(a*d - b*c)
if near(denom, 0):
# parallel
# If collinear, the equation is solvable with t = 0.
# When t=0, s would have to equal e/b and f/d
if near(float(e)/b, float(f)/d):
# collinear
px = x1
py = y1
else:
return None
else:
t = (e*d - b*f)/denom
# s = (a*f - e*c)/denom
px = x1 + t*(x2-x1)
py = y1 + t*(y2-y1)
return px, py
def crosses(line1, line2):
"""
Return True if line segment line1 intersects line segment line2 and
line1 and line2 are not parallel.
"""
(x1,y1), (x2,y2) = line1
(u1,v1), (u2,v2) = line2
(a,b), (c,d) = (x2-x1, u1-u2), (y2-y1, v1-v2)
e, f = u1-x1, v1-y1
denom = float(a*d - b*c)
if near(denom, 0):
# parallel
return False
else:
t = (e*d - b*f)/denom
s = (a*f - e*c)/denom
# When 0<=t<=1 and 0<=s<=1 the point of intersection occurs within the
# line segments
return 0<=t<=1 and 0<=s<=1
def near(a, b, rtol=1e-5, atol=1e-8):
return abs(a - b) < (atol + rtol * abs(b))
line1 = ((4,4),(10,10))
line2 = ((11,5),(5,11))
line3 = ((11,5),(9,7))
line4 = ((4,0),(10,6))
assert all(near(a,b) for a,b in zip(line_intersection(line1,line2), (8.0, 8.0)))
assert all(near(a,b) for a,b in zip(line_intersection(line1,line3), (8.0, 8.0)))
assert all(near(a,b) for a,b in zip(line_intersection(line2,line3), (11, 5)))
assert line_intersection(line1, line4) == None # parallel, non-collinear
assert crosses(line1,line2) == True
assert crosses(line2,line3) == False