12 KiB
用矩阵分割曲线
另一种分割曲线的方法是利用贝塞尔曲线的矩阵表示。矩阵一章已经说明可以用矩阵乘法表示曲线，尤其是以下两种分别表示二次曲线和三次曲线的形式（为提高可读性，贝塞尔曲线的系数向量已被倒转次序）：
[ B(t) = \begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]
和
[ B(t) = \begin{bmatrix} 1 & t & t^2 & t^3 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 & 0\ -3 & 3 & 0 & 0\ 3 & -6 & 3 & 0\ -1 & 3 & -3 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \ P_4 \end{bmatrix} ]
假设要在点t = z处分割曲线得到两条新的（且显然更小的）贝塞尔曲线，则可以用矩阵表示和一点线性代数求出这两条贝塞尔曲线的坐标。首先将实际的“线上点”信息分离到新的矩阵乘法中：
[ B(t) = \begin{bmatrix} 1 & (z \cdot t) & (z \cdot t)^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix}
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ 0 & z & 0 \ 0 & 0 & z^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]
以及
[ B(t) = \begin{bmatrix} 1 & (z \cdot t) & (z \cdot t)^2 & (z \cdot t)^3 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 & 0 \ -3 & 3 & 0 & 0 \ 3 & -6 & 3 & 0 \ -1 & 3 & -3 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \ P_4 \end{bmatrix}
\begin{bmatrix} 1 & t & t^2 & t^3 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 & 0\ 0 & z & 0 & 0\ 0 & 0 & z^2 & 0\ 0 & 0 & 0 & z^3 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 & 0 \ -3 & 3 & 0 & 0 \ 3 & -6 & 3 & 0 \ -1 & 3 & -3 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \ P_4 \end{bmatrix} ]
如果可以将这些矩阵组合成**[t值] · [贝塞尔矩阵] · [列矩阵]**的形式且前两项保持不变，那么右侧的列矩阵即为描述从t = 0到t = z的第一段新的贝塞尔曲线的坐标。利用线性代数的一些简单的法则可以很轻松地做到这一点。（如果不在乎推导过程，那么可以直接跳到方框底部得到结果！）
推导新的凸包坐标
推导分割曲线后所得两段曲线的坐标要花上几步，而且曲线次数越高，花的工夫越多，因此先看二次曲线：
[ B(t) = \begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ 0 & z & 0 \ 0 & 0 & z^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]
[
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \underbrace{\kern 2.25em Z \cdot M \kern 2.25em}_{\textit{将这一项……}} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]
[
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \underbrace{ M \cdot M^{-1} \cdot Z \cdot M }_{\textit{变为这一项后……}} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]
[
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot M \underbrace{ \kern 1.25em \cdot \kern 1.25em Q \kern 1.25em \cdot \kern 1.25em}_{\textit{……得到这一项！}} \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]
以上变形可行是因为[M · M-1]为单位矩阵。这有点像在计算中让某项乘以x/x——不改变函数本身，却可以将函数改写为更好处理的形式或者得到不同的分解。类似地将上式中的矩阵左乘以[M · M-1]不会影响整个式子，却可以将矩阵序列[某项 · M]变为[M · 某项]，而这至关重要——如果知道了[M-1 · Z · M]是什么，那就可以将其施加到已有坐标上得到一条二次贝塞尔曲线的标准矩阵表示（即[T · M · P]）)和表示从t = 0到t = z的曲线的一系列新坐标。计算如下：
[ Q = M^{-1} \cdot Z \cdot M = \begin{bmatrix} 1 & 0 & 0 \ 1 & \frac{1}{2} & 0 \ 1 & 1 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ 0 & z & 0 \ 0 & 0 & z^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix}
\begin{bmatrix} 1 & 0 & 0 \ -(z-1) & z & 0 \ (z - 1)^2 & -2 \cdot (z-1) \cdot z & z^2 \end{bmatrix} ]
很好！现在得出新的二次曲线：
[ B(t) = \begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot M \cdot Q \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix}
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot M \cdot \left ( Q \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} \right ) ]
[
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \left ( \begin{bmatrix} 1 & 0 & 0 \ -(z-1) & z & 0 \ (z - 1)^2 & -2 \cdot (z-1) \cdot z & z^2 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} \right ) ]
[
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ z \cdot P_2 - (z-1) \cdot P_1 \ z^2 \cdot P_3 - 2 \cdot z \cdot (z-1) \cdot P_2 + (z - 1)^2 \cdot P_1 \end{bmatrix} ]
非常好——如果需要从t = 0到t = z的子曲线，那么只需保持第一个坐标不变（很合理），控制点变为原有控制点和起点关于z的分比的平均点，而且新的终点为平均点，其比例与二次伯恩斯坦多项式莫名地相似。这些新坐标其实非常容易直接计算得到！
当然这只是两条曲线中的一条，得到从t = z到t = 1的一段需要再算一次。首先注意到之前的计算其实是在一般的区间[0,z]上进行的。之所以可以写成更简单的形式是因为0为端点，但将0显式地写出可知真正所计算的是：
[ B(t) = \begin{bmatrix} 1 & ( 0 + z \cdot t) & ( 0 + z \cdot t)^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]
[
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ 0 & z & 0 \ 0 & 0 & z^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]
如果需要[z,1]区间，那么计算如下：
[ B(t) = \begin{bmatrix} 1 & ( z + (1-z) \cdot t) & ( z + (1-z) \cdot t)^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]
[
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & z & z^2 \ 0 & 1-z & 2 \cdot z \cdot (1-z) \ 0 & 0 & (1-z)^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} ]
用同样的技巧左乘单位矩阵将[某项 · M]变为[M · 某项]：
[ Q' = M^{-1} \cdot Z' \cdot M = \begin{bmatrix} 1 & 0 & 0 \ 1 & \frac{1}{2} & 0 \ 1 & 1 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & z & z^2 \ 0 & 1-z & 2 \cdot z \cdot (1-z) \ 0 & 0 & (1-z)^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix}
\begin{bmatrix} (z-1)^2 & -2 \cdot z \cdot (z-1) & z^2 \ 0 & -(z-1) & z \ 0 & 0 & 1 \end{bmatrix} ]
那么最终第二条曲线为：
[ B(t) = \begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot M \cdot Q \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix}
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot M \cdot \left ( Q' \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} \right ) ]
[
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \left ( \begin{bmatrix} (z-1)^2 & -2 \cdot z \cdot (z-1) & z^2 \ 0 & -(z-1) & z \ 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix} \right ) ]
[
\begin{bmatrix} 1 & t & t^2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 \ -2 & 2 & 0 \ 1 & -2 & 1 \end{bmatrix} \cdot \begin{bmatrix} z^2 \cdot P_3 - 2 \cdot z \cdot (z-1) \cdot P_2 + (z-1)^2 \cdot P_1 \ z \cdot P_3 - (z-1) \cdot P_2 \ P_3 \end{bmatrix} ]
***很好。*出现了与之前相同的情形：保持最后一个坐标不变（很合理），控制点变为原有控制点和终点关于z的分比的平均点，而且新的终点为平均点，其比例与二次伯恩斯坦多项式莫名地相似，只不过这次用的是z-1而不是1-z。这些新坐标也非常容易直接计算得到！
因此，不用德•卡斯特如算法而用线性代数可知在点t = z处分割一条二次曲线可得两条子曲线，它们均为用容易求得的坐标所描述的贝塞尔曲线：
[ \begin{bmatrix} 1 & 0 & 0 \ -(z-1) & z & 0 \ (z - 1)^2 & -2 \cdot (z-1) \cdot z & z^2 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix}
\begin{bmatrix} P_1 \ z \cdot P_2 - (z-1) \cdot P_1 \ z^2 \cdot P_3 - 2 \cdot z \cdot (z-1) \cdot P_2 + (z - 1)^2 \cdot P_1 \end{bmatrix} ]
和
[ \begin{bmatrix} (z-1)^2 & -2 \cdot z \cdot (z-1) & z^2 \ 0 & -(z-1) & z \ 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \end{bmatrix}
\begin{bmatrix} z^2 \cdot P_3 - 2 \cdot z \cdot (z-1) \cdot P_2 + (z-1)^2 \cdot P_1 \ z \cdot P_3 - (z-1) \cdot P_2 \ P_3 \end{bmatrix} ]
虽然三次曲线可以同理推导，但此处省略实际的推导过程（读者可自行写出）并直接展示所得的新坐标集：
[ \begin{bmatrix} 1 & 0 & 0 & 0 \ -(z-1) & z & 0 & 0 \ (z-1)^2 & -2 \cdot (z-1) \cdot z & z^2 & 0 \ -(z-1)^3 & 3 \cdot (z-1)^2 \cdot z & -3 \cdot (z-1) \cdot z^2 & z^3 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \ P_4 \end{bmatrix}
\begin{bmatrix} P_1 \ z \cdot P_2 - (z-1) \cdot P_1 \ z^2 \cdot P_3 - 2 \cdot z \cdot (z-1) \cdot P_2 + (z-1)^2 \cdot P_1 \ z^3 \cdot P_4 - 3 \cdot z^2 \cdot (z-1) \cdot P_3 + 3 \cdot z \cdot (z-1)^2 \cdot P_2 - (z-1)^3 \cdot P_1 \end{bmatrix} ]
和
[ \begin{bmatrix} -(z-1)^3 & 3 \cdot (z-1)^2 \cdot z & -3 \cdot (z-1) \cdot z^2 & z^3 \ 0 & (z-1)^2 & -2 \cdot (z-1) \cdot z & z^2 \ 0 & 0 & -(z-1) & z \ 0 & 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} P_1 \ P_2 \ P_3 \ P_4 \end{bmatrix}
\begin{bmatrix} z^3 \cdot P_4 - 3 \cdot z^2 \cdot (z-1) \cdot P_3 + 3 \cdot z \cdot (z-1)^2 \cdot P_2 - (z-1)^3 \cdot P_1 \ z^2 \cdot P_4 - 2 \cdot z \cdot (z-1) \cdot P_3 + (z-1)^2 \cdot P_2 \ z \cdot P_4 - (z-1) \cdot P_3 \ P_4 \end{bmatrix} ]
对于以上矩阵而言，是否真的有必要计算第二段的矩阵？其实不然。有了第一段的矩阵就意味着有了第二段的：将矩阵Q每行的非零值推到右侧，左侧的空位补零，再将矩阵上下翻转，**Q'**就“计算”出来了。搞定！
如此实现曲线分割需要的迭代更少，且只用缓存值直接进行四则运算，因此对于迭代耗费较大的系统更为划算。如果使用擅长矩阵操作的设备进行计算，那么用这种方法切割贝塞尔曲线会比使用德•卡斯特如算法快得多。