绘图实战二:编程求平面线段的交点-克拉默法则与向量积法

已知 2D 平面上两条线段的四个端点 a b c d,如何编码求出线段 ab 和 cd 的交点?



作为数学问题来讲,并不复杂,只需建立二元一次方程组,求解未知数即可,但如何编码实现呢 ? 一般来说有以下几种方法:

1:克拉默法则解方程组;
2:空间向量的向量积求解;(可以看做是对克拉默法则的证明,最终得到的结论与直接使用克拉默法则并无差别)
3:通过空间向量的代数计算求解,最简洁,高效
4:模拟手算求解方程组的过程。

相对来说,方法 3 是最佳实践,网上的很多代码都是基于方案 3 实现的;最不推荐方法 4,因为手算过程并不好模拟,代码也很难写优雅。方法 1、2 的缺点是无法求空间直线的交点,这一缺点方案 4 同样存在。接下来,我会先给出详细的数学证明,推导出公式;然后给出代码实现。

基于克拉默法则或者空间向量叉乘


这两种方法,都是基于系数矩阵计算的,所以第一步,是通过四个端点得到直线方程的一般式:


Ax + By + C = 0

以线段 ab 为例,假设 a(x1, y1), b(x2, y2),那么我们可以用两点式建立方程:

然后与 Ax + By + C = 0 进行系数对照即可:

克拉默法则

求得系数 A、 B、 C 后,接下来就很简单了,可以直接套用克拉默法则,建立行列式 D, D1, D2,求解即可,但需要注意,系数矩阵的行列式 D != 0,才有解,如果 D = 0,则矩阵 D 不可逆,对应的向量组线性相关,两条直线要么平行,要么重叠。这一点在写代码时,可以优先判断。下图是克拉默法则的求解过程:

这样得到的最终解即方程组的解,也就是两条直线的交点,得到结论后,代码实现会很简单,就是对系数进行加减乘除;但是要注意,这里得出的是直线的交点,即线段所在的直线交点,并不是线段的交点,接下来还需要验证,交点是否在线段上,这个实现代码的时候再加。

空间向量向量积(叉乘法)

这种方法可以看做是对克拉默法则的证明,最终会得到和克拉默法则相同的结论,下面尽最大努力证明;第一,我们要将平面直线方程,看做是三维空间的一个 Z=1的二维平面:


Ax + By + C = 0,可以看做: Ax + By + Cz = 0; 其中 z = 1

那么两个方程就是两个空间平面,空间平面的法向量为 n1 = (A1, B1, C1),n2 = (A2, B2, C2),然后计算 n1,n2 的向量积 m,那么向量 m 就是垂直于 n1,n2 的向量,该向量便是两个平面交线的方向向量,然后让 m 向量的 z 分量归一,即 m/z,所得的 x, y 分量便是所求。光描述,很难理解,直接看图:

上图的两个竖直的平面,即两个线性方程组,将 z=1 看做是第三维度,就是三维空间的两个平面,空间平面方程其法向量就是方程的系数(A, B, C),两个法向量的向量积就是两个平面交线的方向向量 m。那么向量 m 与 XOY 平面的交点,即使所求。向量积的结果依然是向量,更多关于向量积

向量积的运算

三维向量积的运算,需要借助三阶行列式:

代码实现

已经得到了交点坐标与系数之间的关系,代码实现就简单了,先建立 Line 的结构体,同时判断直线交点是否在线段上:

然后实现交点判断的函数:

由于篇幅过长,空间向量代数计算得到交点的方法,另起一篇。

点赞