系数判据 · 点到直线
平行、垂直与距离
两条直线的关系只有三种:平行(含重合)、垂直、以及一般的相交。判据可以写在斜率上,也可以写在一般式的系数上。两种写法在能用时等价,而系数写法少掉一整套分情形。
1 · 两种判据
设
l1:A1x+B1y+C1=0、l2:A2x+B2y+C2=0。
定理 1.1
l1∥l2(含重合)当且仅当
A1B2−A2B1=0;l1⊥l2
当且仅当
A1A2+B1B2=0。
平行判据说的是两个方向向量
(B1,−A1)
与
(B2,−A2)
共线,垂直判据说的是两个法向量
(A1,B1)
与
(A2,B2)
数量积为零。两式都是多项式,没有分母。
斜率写法则要分情形。k1=k2
只在两条直线都有斜率时可用;k1k2=−1
更窄——x=1
与
y=2
显然垂直,但前者斜率不存在、后者斜率为
0,这个乘积无从代入。课本把「一条竖直一条水平」单列为垂直的一种情形,而系数判据里它只是
1⋅0+0⋅1=0。
2 · 交点与系数行列式
联立两个方程,解得交点的坐标,分母都是行列式
det=A1B2−A2B1。这正是平行判据里的那个量:平行时
det=0,方程组无唯一解。
det
不只是「是否为零」的开关,它的大小还度量结果的可信度。取
l1:x+y−1=0
与
l2:x+(1+ε)y−2=0,两线夹角随
ε
缩小而趋于零,实测交点坐标:
|
ε
|
det
|
交点横坐标 |
|
10−3
|
1.0×10−3
|
−999.00
|
|
10−6
|
1.0×10−6
|
−9.99999×105
|
|
10−9
|
1.0×10−9
|
−9.9999992×108
|
|
10−15
|
1.1×10−15
|
−9.007×1014
|
|
0
|
0
|
−∞
|
ε=10−9
那一行已经丢掉八位有效数字:真值是
−109
附近的一个数,算出来的却是
−999999916.26。浮点数不是在恰好平行处才失效,而是一路失准过去的。intersect 因此在
∣det∣
低于容差时直接返回 null,把「平行或重合」交给调用方处理,而不是把一个量级
1014
的坐标交出去。
图 2-1 · 两条直线的关系。可拖动各自的倾斜角与位置,读数给出行列式、交点、夹角;两线平行时给出它们的距离。
3 · 点到直线的距离
定理 3.1 点
P0(x0,y0)
到直线
Ax+By+C=0
的距离为
d=A2+B2∣Ax0+By0+C∣
分子是把点代入方程左端所得的值,它的符号还标出点落在直线的哪一侧;分母是法向量的长度,作用是把这个值换算成真正的距离。P0
在直线上时分子为零。
竖直线与水平线不必单列:x−2=0
到点
(5,7)
的距离是
1∣5−2∣=3,代进同一个公式即得。
4 · 两平行线的距离要先归一化
两条平行线的距离等于其中一条上任取一点到另一条的距离。若两式的系数已经完全相同,公式简化为
A2+B2∣C1−C2∣——前提是系数相同,而这个前提最容易漏掉。
取
l1:3x+4y−10=0
与
l2:6x+8y+5=0。两者平行,照上式直接算得
5∣−10−5∣=3,而真值是
2.5:l2
的系数是
l1
的两倍,两个常数项不在同一把尺子上。把
l2
归一化成
3x+4y+2.5=0
再算得
5∣−10−2.5∣=2.5,与「取
l1
上的点
(2,1)
到
l2
的距离」核对一致。
parallelDistance 因此先把两式各自归一化到
A2+B2=1
并固定符号,再取常数项之差。归一化的符号约定(A>0,或
A=0
时
B>0)保证每条直线的归一化结果唯一,否则
3x+4y−10=0
与
−3x−4y+10=0
会给出两个相差符号的常数项,差值随之算错。单测里这条差额是
3
与
2.5,不是舍入量级的偏差,而是错半个身位。
5 · 参考文献
- Distance from a point to a line. Wikipedia. 距离公式的多种推导。https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line
- Cramer's rule. Wikipedia. 二元一次方程组的行列式解法。https://en.wikipedia.org/wiki/Cramer%27s_rule
- Condition number. Wikipedia. 行列式趋零时解的敏感性。https://en.wikipedia.org/wiki/Condition_number