Cardinal 曲线

根据定义，给定点集 \(\{ \mathbf {P}_{k-1}, \mathbf {P}_k, \mathbf {P}_{k+1}, \mathbf {P}_{k+2} \}\) , 则 \(\mathbf {P}_k\) 到 \(\mathbf {P}_{k+1}\) 之间的 Cardinal 曲线可以由如下方程生成：

\[\begin {aligned} \mathbf{P}(u) & = \mathbf{a}u^3 + \mathbf{b}u^2 + \mathbf{c}u + \mathbf{d}\\ \mathbf{d} & =\mathbf {P}_k\\ \mathbf{c} & =s(\mathbf {P}_{k+1}-\mathbf {P}_{k-1})\\ \mathbf{b} & =3(\mathbf {P}_{k+1}-\mathbf {P}_k)-s(\mathbf {P}_{k+2}-\mathbf {P}_k)-2\mathbf{c}\\ \mathbf{a} & =(\mathbf {P}_{k+1}-\mathbf {P}_k) - \mathbf{c} - \mathbf{b} \end {aligned} \]

其中，\(s\) 用于控制曲线的松紧，取值范围为 [0, 1]。 0 表示最紧绷 (无平滑转角)；1 表示最松弛。

绘制思路

根据公式，则只需将 \(u\) 从 0 到 1 采样并依据公式计算坐标即可。不过，由于不好把握 \(u\) 的采样间隔，这里并不打算采用这种方案。

我的思路是：

先计算两点之间 x, y 方向的差值
取差值绝对值较大的那个值，按预设精度进行细分，计算出 \(u\) 的步长
根据 \(u\) 的步长，计算方程的增量 \(\Delta \mathbf{P}\)
采用前向差分法，依次计算中间点坐标
a. 如果中间点到上一线段的距离小于预设精度，抛弃该点

前向差分

设有一个三次样条曲线，其表达式如下：

\[\mathbf {P}(u) = \mathbf{a}u^3 + \mathbf{b}u^2 + \mathbf{c}u + \mathbf {d} \]

如果将 \(u\) 的取值范围细分为具有固定大小 \(h\) 的子区间，则相邻两点 \(x\) 坐标为：

\[\begin{aligned} x_k &= x(u_k) \\ x_{k+1} &= x(u_k + h) \end{aligned} \]

可计算出前向差分为：

\[\begin{aligned} \Delta_1 x_k &= x_{k+1} - x_k \\ & = 3\mathbf {a} hu^2_k + (3\mathbf{a}h^2 + 2\mathbf{b}h)u_k + (\mathbf{a}h^3 + \mathbf{b}h^2 + \mathbf{c}h) \end{aligned} \]

由于 \(\Delta_1 x_k\) 是关于 \(u\) 的多项式，计算复杂，所以也可以计算出 \(\Delta_1 x_k\) 的增量 \(\Delta_2 x_k\)，这样即可用加法计算出 \(\Delta_1 x_k\) 的值。不断重复计算增量的过程，直到增量为常数。最终可以得到：

\[\begin{aligned} \Delta_1 x_k &= 3\mathbf {a} hu^2_k + (3\mathbf{a}h^2 + 2\mathbf{b}h)u_k + (\mathbf{a}h^3 + \mathbf{b}h^2 + \mathbf{c}h) \\ \Delta_2 x_k &= 6\mathbf {a} h^2u_k +6\mathbf{a}h^3 + 2\mathbf{b}h^2\\ \Delta_3 x_k &= 6\mathbf{a}h^3 \end{aligned} \]

根据以上公式，从 \(u_0=0\) 开始，步长为 \(h\)，\(x\) 坐标的迭代过程为：

\(k\)	\(\Delta_3 x_k\)	\(\Delta_2 x_k\)	\(\Delta_1 x_k\)	\(x_k\)
0	\(6\mathbf{a}h^3\)	\(6\mathbf{a}h^3 + 2\mathbf{b}h^2\)	\(\mathbf {a}h^3 + \mathbf {b}h^2 + \mathbf {c}h\)	\(\mathbf {d}\)
1	\(6\mathbf{a}h^3\)	\(\Delta_2 x_0 + \Delta_3 x_0\)	\(\Delta_1 x_0 + \Delta_2 x_0\)	\(x_0+\Delta_1 x_0\)
\(\vdots\)
\(k\)	\(6\mathbf{a}h^3\)	\(\Delta_2 x_{k-1} + \Delta_3 x_{k-1}\)	\(\Delta_1 x_{k-1} + \Delta_2 x_{k-1}\)	\(x_{k-1} + \Delta x_{k-1}\)
可以看到，每次迭代只需计算 3 次加法。