De Casteljau算法
维基百科,自由的百科全书
数学子领域数值分析中的de Casteljau算法,以发明者Paul de Casteljau命名,是计算伯恩斯坦形式的多项式或貝茲曲線的递归方法。
虽然对于大部分的体系结构,该算法和直接方法相比较慢,但它在数值上更为稳定。
目录 |
[编辑] 定义
以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 [[0,0],[1,1],[0,1],[1,0]] > 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
[编辑] 参看
- Horner法:计算单项式形式多项式
- Clenshaw算法:计算切比雪夫形式多项式