# 德卡斯特里奥算法

（重定向自De Casteljau算法

## 定义

${\displaystyle B(t)=\sum _{i=0}^{n}\beta _{i}b_{i,n}(t)}$,

${\displaystyle b_{i,n}(t)={n \choose i}(1-t)^{n-i}t^{i}}$.

${\displaystyle \beta _{i}^{(0)}:=\beta _{i}{\mbox{ , }}i=0,\ldots ,n}$
${\displaystyle \beta _{i}^{(j)}:=\beta _{i}^{(j-1)}(1-t_{0})+\beta _{i+1}^{(j-1)}t_{0}{\mbox{ , }}i=0,\ldots ,n-j{\mbox{ , }}j=1,\ldots ,n}$

${\displaystyle B(t_{0})=\beta _{0}^{(n)}.}$

${\displaystyle \beta _{0}^{(0)},\beta _{0}^{(1)},\ldots ,\beta _{0}^{(n)}}$
${\displaystyle \beta _{0}^{(n)},\beta _{1}^{(n-1)},\ldots ,\beta _{n}^{(0)}}$

## 注意事项

${\displaystyle {\begin{matrix}\beta _{0}&=\beta _{0}^{(0)}&&&\\&&\beta _{0}^{(1)}&&\\\beta _{1}&=\beta _{1}^{(0)}&&&\\&&&\ddots &\\\vdots &&\vdots &&\beta _{0}^{(n)}\\&&&&\\\beta _{n-1}&=\beta _{n-1}^{(0)}&&&\\&&\beta _{n-1}^{(1)}&&\\\beta _{n}&=\beta _{n}^{(0)}&&&\\\end{matrix}}}$

${\displaystyle B(t)=\sum _{i=0}^{n}\beta _{i}^{(0)}b_{i,n}(t){\mbox{ , }}\qquad t\in [0,1]}$

${\displaystyle B_{1}(t)=\sum _{i=0}^{n}\beta _{0}^{(i)}b_{i,n}\left({\frac {t}{t_{0}}}\right){\mbox{ , }}\qquad t\in [0,t_{0}]}$

${\displaystyle B_{2}(t)=\sum _{i=0}^{n}\beta _{i}^{(n-i)}b_{i,n}\left({\frac {t-t_{0}}{1-t_{0}}}\right){\mbox{ , }}\qquad t\in [t_{0},1]}$

## 例子

${\displaystyle \beta _{0}^{(0)}=\beta _{0}}$
${\displaystyle \beta _{1}^{(0)}=\beta _{1}}$
${\displaystyle \beta _{2}^{(0)}=\beta _{2}}$

t0点计算。

${\displaystyle \beta _{0}^{(1)}=\beta _{0}^{(0)}(1-t_{0})+\beta _{1}^{(0)}t=\beta _{0}(1-t_{0})+\beta _{1}t_{0}}$
${\displaystyle \beta _{1}^{(1)}=\beta _{1}^{(0)}(1-t_{0})+\beta _{2}^{(0)}t=\beta _{1}(1-t_{0})+\beta _{2}t_{0}}$

${\displaystyle {\begin{matrix}\beta _{0}^{(2)}&=&\beta _{0}^{(1)}(1-t_{0})+\beta _{1}^{(1)}t_{0}\\\ &=&\beta _{0}(1-t_{0})(1-t_{0})+\beta _{1}t_{0}(1-t_{0})+\beta _{1}(1-t_{0})t_{0}+\beta _{2}t_{0}t_{0}\\\ &=&\beta _{0}(1-t_{0})^{2}+2\beta _{1}t_{0}(1-t_{0})+\beta _{2}t_{0}^{2}\\\end{matrix}}}$

## 贝塞尔曲線

${\displaystyle \mathbf {B} (t)=\sum _{i=0}^{n}\mathbf {P} _{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]}$

${\displaystyle \mathbf {P} _{i}:={\begin{pmatrix}x_{i}\\y_{i}\\z_{i}\end{pmatrix}}}$.

${\displaystyle B_{1}(t)=\sum _{i=0}^{n}x_{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]}$
${\displaystyle B_{2}(t)=\sum _{i=0}^{n}y_{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]}$
${\displaystyle B_{3}(t)=\sum _{i=0}^{n}z_{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]}$

## 伪代码例子

    global max_level = 5
procedure draw_curve(P1, P2, P3, P4, level)
if (level > max_level)
draw_line(P1, P4)
else
L1 = P1
L2 = midpoint(P1, P2)
H  = midpoint(P2, P3)
R3 = midpoint(P3, P4)
R4 = P4
L3 = midpoint(L2, H)
R2 = midpoint(R3, H)
L4 = midpoint(L3, R2)
R1 = L4
draw_curve(L1, L2, L3, L4, level + 1)
draw_curve(R1, R2, R3, R4, level + 1)
end procedure draw_curve


## 代码实现

用线性插值计算P和Q之间的一点R，插值参数为t

P = 代表一个点的表
Q = 代表一个点的表
t = 线性插值的参数值, t<-[0..1]

>	linearInterp :: [Float]->[Float]->Float->[Float]
>	linearInterp [] [] _ = []
>	linearInterp (p:ps) (q:qs) t = (1-t)*p + t*q : linearInterp ps qs t

t = 线性插值的参数值, t<-[0..1]
b = 控制点的表

>	eval :: Float->[[Float]]->[[Float]]
>	eval t（bi:bj:[]）= [linearInterp bi bj t]
>	eval t (bi:bj:bs) = (linearInterp bi bj t) : eval t (bj:bs)

t = 线性插值的参数值, t<-[0..1]
b = 控制点的表

>	deCas :: Float->[[Float]]->[Float]
>	deCas t（bi:[]）= bi
>	deCas t bs = deCas t (eval t bs)

n = 要计算的点的个数
b = Bezier控制点列表

>	bezierCurve :: Int->[[Float]]->[[Float]]
>	bezierCurve n b = [deCas (fromIntegral x / fromIntegral n) b | x<-[0 .. n] ]


### Python

（该代码用到Python图像库

import Image
import ImageDraw

SIZE=128
image = Image.new("RGB", (SIZE, SIZE))
d = ImageDraw.Draw(image)

def midpoint((x1, y1), (x2, y2)):
return ((x1+x2)/2, (y1+y2)/2)

MAX_LEVEL = 5
def draw_curve(P1, P2, P3, P4, level=1):
if level == MAX_LEVEL:
d.line((P1, P4))
else:
L1 = P1
L2 = midpoint(P1, P2)
H  = midpoint(P2, P3)
R3 = midpoint(P3, P4)
R4 = P4
L3 = midpoint(L2, H)
R2 = midpoint(R3, H)
L4 = midpoint(L3, R2)
R1 = L4
draw_curve(L1, L2, L3, L4, level+1)
draw_curve(R1, R2, R3, R4, level+1)

draw_curve((10,10),(100,100),(100,10),(100,100))

image.save(r"c:\DeCasteljau.png", "PNG")

print "ok."


## 参考

• Farin, Gerald & Hansford, Dianne (2000). The Essentials of CAGD. Natic, MA: A K Peters, Ltd. ISBN 1-56881-123-3