德卡斯特里奧算法

數學子領域數值分析中的德卡斯特里奧算法（De Casteljau's algorithm），以發明者保爾·德·卡斯特里奧命名，是計算伯恩斯坦形式的多項式或貝濟埃曲線的遞歸方法。雖然對於大部分的體系結構，該算法和直接方法相比較慢，但它在數值上更為穩定。

基本介紹

• 中文名：德卡斯特里奧算法
• 外文名：De Casteljau's algorithm
• 領域：數值分析
• 分類：算法、樣條

定義

貝茲曲線B（角度為n，控制點）可用以下方式運用德卡斯特里奧算法：

其中，b為伯恩施坦基本多項式。

曲線在t0點上可以用遞推關係式運算。

然後，在點上的計算可以此算法的 步計算。 的結果為：

再者，貝茲曲線可在分成帶有各種控制點的兩段曲線：

注意事項

進行手算時把係數寫成三角形形式很有用。

當選擇一點t0來計算波恩斯坦多項式時，我們可以用三角形形式的兩個對角線來構造多項式的分段表示。

把它變成

以及

例子

我們要計算2次波恩斯坦多項式，其伯恩斯坦係數為

在t0點計算。

我們有下式開始遞歸

遞歸的第二次重複結束於

這就是我們所預料的n階伯恩斯坦多項式。

貝塞爾曲線

在計算帶n+1個控制點Pi的三維空間中的n次貝塞爾曲線 (Bézier curve) 時：

其中，

我們把Bézier曲線分成三個分立的方程：

然後我們用de Casteljau算法分別計算。

偽代碼例子

這是一個遞歸的畫出一條從點P1到P4，彎向P2和P3的曲線的偽代碼例子。級數參數是遞歸的次數。該過程用增加了的級數參數來遞歸的調用它自己。當級別達到最大級別這個全局變數時，在P1和P4之間就畫上直線。函式中點（midpoint）去兩個點，並返回這兩點間的線段的中點。

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

代碼實現

Haskell

用線性插值計算P和Q之間的一點R，插值參數為t用法：linearInterp P Q t          P = 代表一個點的表          Q = 代表一個點的表          t = 線性插值的參數值, t<-[0..1]返回：代表點（1-t）P + tQ的表>    linearInterp :: [Float]->[Float]->Float->[Float]>    linearInterp [] [] _ = []>    linearInterp (p:ps) (q:qs) t = (1-t)*p + t*q : linearInterp ps qs t計算一對控制點間的線性插值的中間結果用法：eval t b          t = 線性插值的參數值, t<-[0..1]          b = 控制點的表返回：對n個控制點，返回n-1個插值點的表>    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)用de Casteljau算法計算Bezier曲線上一點用法：deCas t b          t = 線性插值的參數值, t<-[0..1]          b = 控制點的表返回：代表Bezier曲線上一個點的列表>    deCas :: Float->[[Float]]->[Float]>    deCas t（bi:[]）= bi>    deCas t bs = deCas t (eval t bs)用de Casteljau算法計算沿著Bezier曲線的一系列點。點用一個列表返回。用法：bezierCurve n b         n = 要計算的點的個數         b = Bezier控制點列表返回：Bezier曲線上n+1個點例子：bezierCurve 50 <nowiki>[[0,0]，[1,1]，[0,1]，[1,0]]</nowiki>>    bezierCurve :: Int->[[Float]]->[[Float]]>    bezierCurve n b = [deCas (fromIntegral x / fromIntegral n) b | x<-[0 .. n] ]

Python

import Imageimport ImageDrawSIZE=128image = Image.new("RGB", (SIZE, SIZE))d = ImageDraw.Draw(image)def midpoint((x1, y1), (x2, y2)):    return ((x1+x2)/2, (y1+y2)/2)MAX_LEVEL = 5def 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."