本文仅简述Bezier曲线的公式推导，并给出了一种代码实现。在阅读本文之前，请确保你已经对Bezier曲线的背景知识有所了解。相关知识可以通过以下课程进行学习：MOOC-计算机图形学-中国农业大学-赵明或者观看B站搬运版。
算法原理
给定
n
+
1
n+1
n+1个控制点
P
i
(
i
=
0
,
1
,
⋯
,
n
)
P_i(i=0,1,\cdots,n)
Pi(i=0,1,⋯,n)，构造多项式函数
P
(
u
)
=
∑
i
=
0
n
P
i
⋅
B
E
Z
i
,
n
(
u
)
,
0
⩽
u
⩽
1
，
(1)
\mathcal{P}(u)=\sum_{i=0}^{n}P_i\cdot BEZ_{i,n}(u), \quad 0\leqslant u\leqslant 1 \thinspace， \tag{1}
P(u)=i=0∑nPi⋅BEZi,n(u),0⩽u⩽1，(1)
来逼近曲线。其中
B
E
Z
i
,
n
(
u
)
BEZ_{i,n}(u)
BEZi,n(u)称为
n
n
n次Bernstein基函数，且有
B
E
Z
i
,
n
(
u
)
=
C
n
i
u
i
(
1
−
u
)
n
−
i
,
(
i
=
0
,
1
,
⋯
,
n
u
∈
[
0
,
1
]
)
。
(2)
BEZ_{i,n}(u)=C_n^i u^i(1-u)^{n-i}, \quad \left(\begin{array}{l} i=0,1,\cdots,n \\ u\in[0,1] \end{array}\right) \thinspace。 \tag{2}
BEZi,n(u)=Cniui(1−u)n−i,(i=0,1,⋯,nu∈[0,1])。(2)
对于公式(1)，函数
P
(
u
)
\mathcal{P}(u)
P(u)将实数区间
[
0
,
1
]
[0,1]
[0,1]映射到实数域上的点集，该点集里的点组成了所求的逼近曲线。
B
E
Z
i
,
n
(
u
)
BEZ_{i,n}(u)
BEZi,n(u)可以看作是控制点
P
i
P_i
Pi在
u
u
u下的权值。因为
B
E
Z
i
,
n
(
u
)
BEZ_{i,n}(u)
BEZi,n(u)具有权性：
∑
i
=
0
n
B
E
Z
i
,
n
(
u
)
≡
1
,
∀
u
∈
(
0
,
1
)
。
(3)
\sum_{i=0}^{n} BEZ_{i,n}(u) \equiv 1, \quad \forall u\in(0,1) \thinspace。\tag{3}
i=0∑nBEZi,n(u)≡1,∀u∈(0,1)。(3)
我们定义：
β
i
(
r
)
=
{
P
i
,
r
=
0
(
1
−
u
)
β
i
(
r
−
1
)
+
u
β
i
+
1
(
r
−
1
)
,
r
=
1
,
2
,
⋯
,
n
，
(4)
\beta_{i}^{(r)} = \begin{cases} P_i, & r = 0 \\ (1-u)\beta_{i}^{(r-1)} + u\beta_{i+1}^{(r-1)}, & r = 1,2,\cdots,n \end{cases} \thinspace， \tag{4}
βi(r)={Pi,(1−u)βi(r−1)+uβi+1(r−1),r=0r=1,2,⋯,n，(4)
其中
i
=
0
,
1
,
⋯
,
n
−
r
i=0,1,\cdots,n-r
i=0,1,⋯,n−r。
可以证明（证明过程参见维基百科De Casteljau算法）：
P
(
u
)
=
∑
i
=
0
n
β
i
(
0
)
⋅
B
E
Z
i
,
n
(
u
)
=
β
0
(
n
)
。
(5)
\mathcal{P}(u) = \sum_{i=0}^{n} \beta_{i}^{(0)}\cdot BEZ_{i,n}(u) = \beta_{0}^{(n)} \thinspace。 \tag{5}
P(u)=i=0∑nβi(0)⋅BEZi,n(u)=β0(n)。(5)
于是得到算法逻辑如下：
- 在实数区间
[
0
,
1
]
[0,1]
[0,1]上大量采样。对于每个样本
u
u
u，计算
P
(
u
)
\mathcal{P}(u)
P(u)。
- 根据公式(5)，我们可以通过计算
β
0
(
n
)
\beta_{0}^{(n)}
β0(n)来计算
P
(
u
)
\mathcal{P}(u)
P(u)。
-
β
0
(
n
)
\beta_{0}^{(n)}
β0(n)可以通过公式(4)进行递归计算。
代码实现
def draw_curve(p_list):
"""
:param p_list: (list of list of int: [[x0, y0], [x1, y1], [x2, y2], ...]) 曲线的控制点坐标列表
:return: (list of list of int: [[x_0, y_0], [x_1, y_1], [x_2, y_2], ...]) 绘制结果的像素点坐标列表
"""
result = []
n = len(p_list) - 1
freq = 1000
for u in range(freq + 1):
u /= freq
tmp = [[p[0], p[1]] for p in p_list]
for r in range(1, n + 1):
tmp = [
[(1 - u) * tmp[i][0] + u * tmp[i + 1][0],
(1 - u) * tmp[i][1] + u * tmp[i + 1][1]
] for i in range(n - r + 1)
]
result.append([round(tmp[0][0]), round(tmp[0][1])])
return result
