问题：现有$n+1$个2维的离散点$P_i=\left(x_i,y_i\right),\left(i=0,1,\cdots ,n\right)$, 如何用$P_i$拟合一条平滑的曲线，最后将曲线分割成数条 2阶/3阶贝塞尔曲线，并保证这数条曲线段拼接处是连续的，即全局可导。

2阶Bezier	3阶Bezier

1 Bezier路径拟合

---

1.1 Bezier曲线绘制原理

Bezier曲线有两个简单的规律:
1、k阶的Bezier曲线需要用到k+1个数据点。 如: 3阶Bezier曲线需要用到4个数据点。
2、Berzier曲线只保证经过起点和终点，不保证经过中间所有的控制点。Berzier曲线用到的第1个数据点和倒数第1个数据点分别被称为起点和终点，中间的所有数据被称为控制点。

关注$P_i$的4个数据点：
$$P_0=\left(x_0,y_0\right),P_1=\left(x_1,y_1\right),P_2=\left(x_2,y_2\right),P_3=\left(x_3,y_3\right)$$

定义向量$t\triangleq 0:\delta t:1$（这是MatLAB的写法， $\delta t$决定曲线绘制精度）。
1阶、2阶、3阶和n阶的Bezier曲线公式分别如下：
$$\begin{array}{rl}{B}_{1st}& =\left(1-t\right)P_0+t{P}_1\\ B_{2nd}& ={\left(1-t\right)}^2{P}_0+2\left(1-t\right)t{P}_1+t^2{P}_2\\ B_{3rd}& ={\left(1-t\right)}^3{P}_0+3{\left(1-t\right)}^{2}t{P}_1+3\left(1-t\right)t^2{P}_2+t^3{P}_3\\ B_{nth}& =\sum _{i=0}^{n}a\left(i\right)\cdot {\left(1-t\right)}^{b\left(i\right)}\cdot t^{c\left(i\right)}\cdot P_i\end{array}\text{\hspace{1em}(1)}$$

其中，
$$\{\begin{array}{rl}a\left(i\right)& =n+1阶杨辉三角第n+1行的第i+1列的数\\ b\left(i\right)& =n-i;c\left(i\right)=i\end{array}$$

下面给出计算$n+1$阶杨辉三角矩阵的Matlab代码

clear all; close all; clc;
n = 5;
YH = zeros(n+1,n+1);
for i = 1:1:n+1
    YH(i,1) = 1; % 第1列元素
    YH(i,i) = 1; % 对角线元素
end

for i = 3:1:n+1 % 从第三行开始，因为前两行都是1
    for j = 2:1:i-1 % 第1列和第i列已经都被赋值为1了
        YH(i,j) = YH(i-1,j-1) + YH(i-1,j);
    end
end

a = YH(n+1,:) % 取n+1行作为系数

% 运行结果 
% n = 0;	1
% n = 1;	1     1
% n = 2;	1     2     1
% n = 3;	1     3     3     1
% n = 4;	1     4     6     4     1
% n = 5;	1     5    10    10     5     1

---

1.2 基于Bezier曲线的路径拟合实验

2阶Bezier曲线绘制如下：

3阶Bezier曲线绘制如下：

n阶-Bezier曲线绘制如下 （n = 10）

实验结果分析：
1、对于$n+1$个离散数据点，用$n$阶的Bezier曲线来路径拟合并不是一个好的选择，很明显，上图的拟合效果很差；
2、用$n$阶Bezier曲线路径拟合会导致运算量暴增，阶次爆炸。
3、除计算量问题外，根据Bezier本身的原理，我们也是无法直接把$n$阶Bezier分割成多个2阶/3阶的贝塞尔曲线的。

要解决本文所提问题，我们只能通过其他的曲线拟合方法先实现路径拟合，然后再把它分割转换成2阶/3阶贝塞尔曲线的描述方式。下面将会介绍BSpline和Catmull_ROM两种曲线拟合方法。

---

2 BSpline路径拟合-分段拼接

通过调研发现，用BSpline曲线来拟合路径，是可以采用分段拼接的方式的，而且它可以保证拼接处是连续的，即全局可导。

2.1 Bspline曲线绘制原理

BSpline曲线有两个简单的规律:
1、k阶的BSpline曲线需要用到k+1个数据点。 如: 3阶BSpline曲线需要用到4个数据点。
2、BSpline曲线的特点是不经过任何数据点（这让我觉得用这个东西搞路径拟合有点离谱）

关注$P_i$的4个数据点：
$$P_0=\left(x_0,y_0\right),P_1=\left(x_1,y_1\right),P_2=\left(x_2,y_2\right),P_3=\left(x_3,y_3\right)$$

定义向量$t\triangleq 0:\delta t:1$（这是MatLAB的写法， $\delta t$决定曲线绘制精度）。
2阶BSpline拟合公式：
$$\{\begin{array}{rl}{a}_0& =\frac{1}{2}\left(x_0+x_1\right)\\ a_1& =x_1-x_0\\ a_2& =\frac{1}{2}\left(x_0-2x_1+x_2\right)\end{array},\{\begin{array}{rl}{b}_0& =\frac{1}{2}\left(y_0+y_1\right)\\ b_1& =y_1-y_0\\ b_2& =\frac{1}{2}\left(y_0-2y_1+y_2\right)\end{array}\text{\hspace{1em}(2)}$$

$$B\left(t\right)=\left(x\left(t\right),y\left(t\right)\right)\Rightarrow \{\begin{array}{rl}x\left(t\right)& =a_0+a_{1}t+a_2{t}^2\\ y\left(t\right)& =b_0+b_{1}t+b_2{t}^2\end{array}\text{\hspace{1em}(3)}$$

3阶BSpline拟合公式：
$$\{\begin{array}{rl}{a}_0& =\frac{1}{6}\left(x_0+4x_1+x_2\right)\\ a_1& =-\frac{1}{2}\left(x_0-x_2\right)\\ a_2& =\frac{1}{2}\left(x_0-2x_1+x_2\right)\\ a_3& =-\frac{1}{6}\left(x_0-3x_1+3x_2-x_3\right)\end{array},\{\begin{array}{rl}{b}_0& =\frac{1}{6}\left(y_0+y{x}_1+y_2\right)\\ b_1& =-\frac{1}{2}\left(y_0-y_2\right)\\ b_2& =\frac{1}{2}\left(y_0-2y_1+y_2\right)\\ b_3& =-\frac{1}{6}\left(y_0-3y_1+3y_2-y_3\right)\end{array}\text{\hspace{1em}(4)}$$

$$B\left(t\right)=\left(x\left(t\right),y\left(t\right)\right)\Rightarrow \{\begin{array}{rl}x\left(t\right)& =a_0+a_{1}t+a_2{t}^2+a_3{t}^3\\ y\left(t\right)& =b_0+b_{1}t+b_2{t}^2+b_3{t}^3\end{array}\text{\hspace{1em}(5)}$$

---

2.2 Bspline分段拼接方法

假设现在有待拟合的n+1个离散点$P_i=\left(x_i,y_i\right),\left(i=0,1,\cdots ,n\right)$ ，采用2阶BSpline分段拼接拟合过程如下：
以$P_0,P_1,P_2$为控制点绘制第1条2阶BSpline
以$P_1,P_2,P_3$为控制点绘制第2条2阶BSpline
…
以$P_{n-2},P_{n-1},P_n$为控制点绘制第n-1条2阶BSpline
由于BSpline曲线不经过任何控制点，我们想让它经过第一个控制$P_0$和最后一个$P_n$控制点 ，则需要修改$P_0$和$P_n$。 注意2阶BSpline曲线与控制点相连线段相切于其中点。

$$\begin{array}{rl}{P}_1-P_0& =P_0-P_0^{\prime }\Rightarrow P_0^{\prime }=2P_0-P_1\\ P_n^{\prime }-P_n& =P_n-P_{n-1}\Rightarrow P_n^{\prime }=2P_n-P_{n-1}\end{array}\text{\hspace{1em}(6)}$$

假设现在有待拟合的n+1个离散点$P_i=\left(x_i,y_i\right),\left(i=0,1,\cdots ,n\right)$ ，采用3阶BSpline分段拼接拟合过程如下：
以$P_0,P_1,P_2,P_3$为控制点绘制第1条3阶BSpline
以$P_1,P_2,P_3,P_4$为控制点绘制第2条3阶BSpline
…
以$P_{n-3},P_{n-2},P_{n-1},P_n$为控制点绘制第n-2条3阶BSpline
由于BSpline不经过任何控制点，我们想让它经过第一个控制$P_0$和最后一个$P_n$控制点 ，则需要修改$P_0$和$P_n$ 。 修改前先描述一下3阶BSpline曲线与控制点之间的关系。

$M_1$ 为$P_0$和$P_2$的中点， $M_2$ 为$P_1$和$P_3$的中点, $P_{1}S=\frac{1}{3}{P}_1{M}_1$， $P_{2}E=\frac{1}{3}{P}_2{M}_2$, $\widetilde{SE}$就是我们通过这4个控制点画出的3阶BSpline曲线。

现在修改为：

$$\{\begin{array}{rl}M& =\frac{1}{2}\left(P_0^{\prime }+P_2\right)\\ 3\left(P_0-P_1\right)& =M-P_1\end{array}\Rightarrow P_0^{\prime }=6P_0-4P_1-P_2\text{\hspace{1em}(7)}$$

同理，
$$P_n^{\prime }=6P_n-4P_{n-1}-P_{n-2}\text{\hspace{1em}(8)}$$

---

2.3 基于BSpline曲线的路径拟合实验

2阶BSpline

2阶Bspline拟合11个数据点（不修改P0和Pn点，双击图片可放大看细节）

2阶Bspline拟合11个数据点（修改P0和Pn点，双击图片可放大看细节）

3阶BSpline

3阶Bspline拟合11个数据点（不修改P0和Pn点，双击图片可放大看细节）

3阶Bspline拟合11个数据点（修改P0和Pn点，双击图片可放大看细节）

实验结果分析：
1、验证了BSpline用分段拼接拟合的可行性，很明显，拟合曲线是全局可导的；
2、拟合精度明显比n阶的Bezier曲线要高。对于$n+1$个离散数据点，现在我们已经用$n-1$条的2阶BSpline曲线或者$n-2$条的3阶BSpline曲线拼接拟合，完成。

现在的问题是如何将2阶和3阶的BSpline曲线用Bezier曲线的描述。

---

2.4 BSpline To Bezier

以2阶为例

2阶Bezier公式如下
$$B_{2nd}={\left(1-t\right)}^2{P}_0+2\left(1-t\right)t{P}_1+t^2{P}_2$$

2阶BSpline公式如下
$$\{\begin{array}{rl}{a}_0& =\frac{1}{2}\left(x_0+x_1\right)\\ a_1& =x_1-x_0\\ a_2& =\frac{1}{2}\left(x_0-2x_1+x_2\right)\end{array},\{\begin{array}{rl}{b}_0& =\frac{1}{2}\left(y_0+y_1\right)\\ b_1& =y_1-y_0\\ b_2& =\frac{1}{2}\left(y_0-2y_1+y_2\right)\end{array}$$

$$B\left(t\right)=\left(x\left(t\right),y\left(t\right)\right)\Rightarrow \{\begin{array}{rl}x\left(t\right)& =a_0+a_{1}t+a_2{t}^2\\ y\left(t\right)& =b_0+b_{1}t+b_2{t}^2\end{array}$$

观察规律， 无论Bezier还是BSpline都是关于$t$的2阶线性函数，因此从原理上他们是可以完全等价的。观察Bezier的公式，$t$的系数完全由控制点$P_0,P_1,P_2$确定，也就是说3个控制可以唯一确定一条2阶的Bezier曲线，那么我们只要求出$P_0,P_1,P_2$就完成了BSpline到Bezier的转换。
令$B\left(t\right)=B_{2nd}$，让$t$的各阶系数分别相等，即可推导出$P_0,P_1,P_2$用$a_0,a_1,a_2,b_0,b_1,b_2$表示的代数表达式:

$$\{\begin{array}{l}{x}_0=a_0\\ \\ x_1=a_0+\frac{1}{2}{a}_1\\ \\ x_2=a_0+a_1+a_2\end{array},\{\begin{array}{l}{y}_0=b_0\\ \\ y_1=b_0+\frac{1}{2}{b}_1\\ \\ y_2=b_0+b_1+b_2\end{array}\text{\hspace{1em}(9)}$$

$$P_0=\left(x_0,y_0\right),P_1=\left(x_1,y_1\right),P_2=\left(x_2,y_2\right)\text{\hspace{1em}(10)}$$

注意：这里的$P_0=\left(x_0,y_0\right)$，并不是原始的需要拟合的数据点。而是用Bezier来等价描述BSpline的数据点。

同理，3阶的转换公式如下：
$$\{\begin{array}{l}{x}_0=a_0\\ \\ x_1=a_0+\frac{1}{3}{a}_1\\ \\ x_2=a_0+\frac{2}{3}{a}_1+\frac{1}{3}{a}_2\\ \\ x_3=a_0+a_1+a_2+a_3\end{array},\{\begin{array}{l}{y}_0=b_0\\ \\ y_1=b_0+\frac{1}{3}{b}_1\\ \\ y_2=b_0+\frac{2}{3}{b}_1+\frac{1}{3}{b}_2\\ \\ y_3=b_0+b_1+b_2+b_3\end{array}\text{\hspace{1em}(11)}$$

$$P_0=\left(x_0,y_0\right),P_1=\left(x_1,y_1\right),P_2=\left(x_2,y_2\right),P_3=\left(x_3,y_3\right)\text{\hspace{1em}(12)}$$

基于BSpline的路径拟合到此结束，BSpline由于其包络性和平滑性，广泛应用于无人驾驶路径规划领域。但由于BSpline不经过任何数据点，在某些特殊情况下，并不适用，因此接下来我们介绍一种经过所有点的曲线拟合方式 Catmull_Rom。

---

3 Catmull_Rom路径拟合-分段拼接

通过调研发现，用Catmull_Rom曲线来拟合路径，也是可以采用分段拼接的方式的，而且它同样可以保证拼接处是连续的，即全局可导，而且它还有一个致命优势，那就是它可以经过所有用于拟合的数据点。

3.1 Catmull_Rom曲线绘制原理

Catmull_Rom曲线有两个特点:
1、Catmull_Rom是3阶线性拟合，至少需要4个数据点；
2、假设我现在用A B C D 4个数据点绘制Catmull_Rom曲线，曲线只会经过B C。

关注$P_i$的4个数据点：
$$P_0=\left(x_0,y_0\right),P_1=\left(x_1,y_1\right),P_2=\left(x_2,y_2\right),P_3=\left(x_3,y_3\right)$$

定义向量$t\triangleq 0:\delta t:1$（这是MatLAB的写法， $\delta t$决定曲线绘制精度）。
Catmull_Rom拟合公式：
$$\{\begin{array}{l}{a}_0=x_1\\ \\ a_1=\frac{1}{2}\left(-x_0+x_2\right)\\ \\ a_2=\frac{1}{2}\left(2x_0-5x_1+4x_2-x_3\right)\\ \\ a_3=\frac{1}{2}\left(-x_0+3x_1-3x_2+x_3\right)\end{array},\{\begin{array}{l}{b}_0=y_1\\ \\ b_1=\frac{1}{2}\left(-y_0+y_2\right)\\ \\ b_2=\frac{1}{2}\left(2y_0-5y_1+4y_2-y_3\right)\\ \\ b_3=\frac{1}{2}\left(-y_0+3y_1-3y_2+y_3\right)\end{array}\text{\hspace{1em}(13)}$$

$$Catmull\_Rom\left(t\right)=\left(x\left(t\right),y\left(t\right)\right)\Rightarrow \{\begin{array}{l}x\left(t\right)=a_0+a_{1}t+a_2{t}^2+a_3{t}^3\\ \\ y\left(t\right)=b_0+b_{1}t+b_2{t}^2+b_3{t}^3\end{array}\text{\hspace{1em}(14)}$$

---

3.2 Catmull_Rom分段拼接方法

前面我们也提到了，假设我现在用A B C D 4个数据点绘制Catmull_Rom曲线，曲线只会经过B C。如果我用B C D E个数据点绘制Catmull_Rom曲线,只会经过C D。如果想让拟合曲线经过所有控制点，则只需要分别在首和尾各添加一个控制点。
添加首尾两点的定义如下：

$$P_s\triangleq \left(x_s,y_s\right),P_e\triangleq \left(x_e,y_e\right)\text{\hspace{1em}(15)}$$

$$\begin{array}{rl}{x}_s& =x_0+\left(x_0-x_1\right)\\ y_s& =y_0+\left(y_0-y_1\right)\\ x_e& =x_n+\left(x_n-x_{n-1}\right)\\ y_e& =y_n+\left(y_n-y_{n-1}\right)\end{array}\text{\hspace{1em}(16)}$$

以$P_s,P_0,P_1,P_2,P_3,\cdots ,P_n,P_e$为待拟合的数据点。

以$P_s,P_0,P_1,P_2$绘制第1条Catmull_Rom曲线
以$P_0,P_1,P_2,P_3$绘制第2条Catmull_Rom曲线
…
以$P_{n-2},P_{n-1},P_n,P_e$为控制点绘制第n条Catmull_Rom曲线

---

3.3 基于Catmull_Rom曲线的路径拟合实验

直接上图

显然，Catmull_Rom曲线的拟合效果是很好的，对于数据点噪声较小的情况，是很适合用这种穿过所有数据点的曲线拟合方式的。

---

3.4 Catmull_Rom To Bezier

本质是 Catmull_Rom也是关于$t$的3阶线性函数，因此从原理上每一条Catmull_Rom曲线段是可以完全等价为3阶的Bezier曲线的。
Catmull_Rom和BSpline都是用$a_0,a_1,a_2,a_3,b_0,b_1,b_2,b_3$作为系数，因此Catmull_Rom的转换公式和3阶BSpline的转换公式一样。
$$\{\begin{array}{l}{x}_0=a_0\\ \\ x_1=a_0+\frac{1}{3}{a}_1\\ \\ x_2=a_0+\frac{2}{3}{a}_1+\frac{1}{3}{a}_2\\ \\ x_3=a_0+a_1+a_2+a_3\end{array},\{\begin{array}{l}{y}_0=b_0\\ \\ y_1=b_0+\frac{1}{3}{b}_1\\ \\ y_2=b_0+\frac{2}{3}{b}_1+\frac{1}{3}{b}_2\\ \\ y_3=b_0+b_1+b_2+b_3\end{array}\text{\hspace{1em}(17)}$$

$$P_0=\left(x_0,y_0\right),P_1=\left(x_1,y_1\right),P_2=\left(x_2,y_2\right),P_3=\left(x_3,y_3\right)\text{\hspace{1em}(18)}$$

参考文献：

https://shenchunxu.blog.csdn.net/article/details/54411098?spm=1001.2014.3001.5506
https://zhuanlan.zhihu.com/p/137539722