【面】计算两线段的交点

直线的一般方程为F(x) = ax+by+c = 0。既然我们已经知道直线的两个点,假设为(x1,y1)(x2,y2),那么可以得到a = y1–y2, b = x2–x1, c = x1y2–x2y1
因此我们可以将两条直线分别表示为:
F1(x) = a1x+b1y+c1 = 0, F2(x) = a2x+b2y+c2 = 0
那么两条线段的交点应该满足
a1x+b1y+c1 = a2x+b2y+c2
由此可推出
x = (b1c2–b2c1)/D
y = (a2c1–a1c2)/D
D = a1b2–a2b1 (D为0时,表示两直线重合)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def segments_insec(x1, y1, x2, y2, x3, y3, x4, y4):
'''
计算两线段交点
'''
a1 = y1 - y2
b1 = x2 - x1
c1 = x1*y2 - x2*y1
a2 = y3 - y4
b2 = x4 - x3
c2 = x3*y4 - x4*y3

D = a1*b2 - a2*b1
if D == 0: # 重合的边线没有交点
return None

x = (b1*c2 - b2*c1)*1.0 / D
y = (a2*c1 - a1*c2)*1.0 / D

# 纠正符号问题
if x == abs(x):
x = abs(x)
if y == abs(y):
y = abs(y)

if (x - x1)*(x - x2) <= 0 and (x - x3)*(x - x4) <= 0: # 判断交点是否在两条线段上
return (x, y)
else: # 交点不在两条线段上除外
return None

print(segments_insec(1,1, 1,-1, -1,0, -2,2))
print(segments_insec(1,1, 1,-1, -1,0, 2,1))
0%