德卡斯特里奥算法

✍ dations ◷ 2024-12-23 19:02:05 #算法,数值分析,样条

数学子领域数值分析中的德卡斯特里奥算法(英语:De Casteljau's algorithm),以发明者保尔·德·卡斯特里奥命名,是计算伯恩斯坦形式的多项式或贝塞尔曲线的递归方法。

虽然对于大部分的体系结构,该算法和直接方法相比较慢,但它在数值上更为稳定。

贝兹曲线(角度为,控制点 β 0 , , β n {\displaystyle \beta _{0},\ldots ,\beta _{n}} 为伯恩施坦基本多项式(英语:Bernstein polynomial)

曲线在0点上可以用递推关系式运算

然后, B {\displaystyle B} 0来计算波恩斯坦多项式时,我们可以用三角形形式的两个对角线来构造多项式的分段表示。

把它变成

以及

我们要计算2次波恩斯坦多项式,其伯恩斯坦系数为

0点计算。

我们有下式开始递归

递归的第二次重复结束于

这就是我们所预料的n阶伯恩斯坦多项式。

在计算带+1个控制点P的三维空间中的次贝塞尔曲线 (Bézier curve) 时

其中

我们把Bézier曲线分成三个分立的方程

然后我们用de Casteljau算法分别计算。

这是一个递归的画出一条从点到,弯向和的曲线的伪代码例子。参数是递归的次数。该过程用增加了的参数来递归的调用它自己。当达到这个全局变量时,在和之间就画上直线。函数去两个点,并返回这两点间的线段的中点。

    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<-返回:代表点(1-t)P + tQ的表>	linearInterp :: ->->Float->>	linearInterp   _ = >	linearInterp (p:ps) (q:qs) t = (1-t)*p + t*q : linearInterp ps qs t计算一对控制点间的线性插值的中间结果用法:eval t b          t = 线性插值的参数值, t<-          b = 控制点的表返回:对n个控制点,返回n-1个插值点的表>	eval :: Float->]->]>	eval t(bi:bj:)= >	eval t (bi:bj:bs) = (linearInterp bi bj t) : eval t (bj:bs)用de Casteljau算法计算Bezier曲线上一点用法:deCas t b          t = 线性插值的参数值, t<-          b = 控制点的表返回:代表Bezier曲线上一个点的列表>	deCas :: 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>,,,]</nowiki>>	bezierCurve :: Int->]->]>	bezierCurve n b =  ]

Python

(该代码用到)

相关

  • 凯斯西储大学蓝色、白色、灰色凯斯西储大学(英语:Case Western Reserve University,简称CWRU),是美国的一所研究型私立大学,位于俄亥俄州的克里夫兰市。该校是由凯斯理工学院(由慈善家伦纳德·
  • N端N端(亦作N-端,英语:N-terminus),又称氮端、氨基端,指多肽链具有游离的α氨基的末端。在转译过程中,多肽链是从N端往C端合成的,因而在书写表示多肽序列时,从N端开始书写,从左到右写到C
  • 分文铁路.mw-parser-output .RMbox{box-shadow:0 2px 2px 0 rgba(0,0,0,.14),0 1px 5px 0 rgba(0,0,0,.12),0 3px 1px -2px rgba(0,0,0,.2)}.mw-parser-output .RMinline{float:none
  • 腓尼基腓尼基(腓尼基语:����‬;英语:Phoenicia;希腊语:Φοινίκη;阿拉伯语:فينيقية‎;埃及语: ())是古代地中海东岸的一个地区,其范围接近于如今的黎巴嫩和叙利亚。为了便于修筑堡垒以
  • 盖墨林数据库盖墨林数据库是一个收录无机化学和金属有机化学化合物和反应的化学数据库。它的前身是德国化学家利奥波德·盖墨林(Leopold Gmelin)于1817年编撰的《盖墨林无机化学手册》(Gmel
  • 反正切反正切(arctangent、 arctan {\displaystyle \arctan } 、arctg、 tan −
  • 梨形钩鲇梨形钩鲇,为辐鳍鱼纲鲇形目甲鲇科的其中一种,为温带淡水鱼,分布于南美洲巴拉那河中游流域,体长可达8.3公分,栖息在底层水域,生活习性不明。 维基物种中有关梨形钩鲇的数据
  • 加布里埃拉·萨巴蒂尼加布里埃拉·萨巴蒂尼(Gabriela Beatriz Sabatini,1970年5月16日-),生于阿根廷首都布宜诺斯艾利斯,昵称“Gaby”,已退役的阿根廷职业女子网球运动员,网球史上的女子GOAT之一,南美洲体
  • 海伦·索莫斯海伦·索莫斯(英语:Helen Sommers;1932年3月29日-2017年3月7日),是美国的民主党政治人物,前华盛顿州众议院(英语:Washington House of Representatives)议员。索莫斯生于新泽西州伍德
  • 刘权之刘权之(1739年-1818年),字云房,湖南长沙人。清朝政治人物。刘权之为乾隆二十四年(1759年)举人,次年联捷进士,改庶吉士,散馆授编修。累升司经局洗马。乾隆四十三年(1778年)出督安徽学政。