德卡斯特里奥算法

✍ dations ◷ 2025-10-19 23:37:58 #算法,数值分析,样条

数学子领域数值分析中的德卡斯特里奥算法(英语: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

(该代码用到)

相关

  • 欧几里得欧几里得(希腊语:Ευκλειδης,前325年-前265年),有时被称为亚历山大里亚的欧几里得,以便区别于墨伽拉的欧几里得,希腊化时代的数学家,被称为“几何学之父”。他活跃于托勒密一
  • 太极太极是中国思想史上的重要概念,主要继承自《周易》:“易有大恒,是生两檥。两檥生四马,四马生八卦。”(马王堆出土本),故改“恒”为“极”,而四马同时改为四象。“太”与“大”古时相
  • 火山学火山学是一门研究火山、熔岩、岩浆及相关地质学、地球物理学、和地球化学现象的学问。研究火山学的人称为火山学家。火山学家是地质学家,他们研究火山的喷发活动和火山的形成
  • 绸,本字写成䌷,是一类丝织品,以平纹织法织成,质薄而软,有花绸、素绸之分。又可细分为宫绸、茧绸、绉绸。绸与绫、罗、缎合称绫罗绸缎。
  • 狂蝇科狂蝇科(学名:Oestridae),亦作肤蝇科,是家蝇下目有瓣类之下的一个科。肤蝇又名人肤蝇,是得名于其物种的幼虫会寄宿于哺乳动物皮肤上的寄生虫。当它把卵产在宿主身上后,孵出来的蛆会
  • 协同物种形成协同物种形成指不同物种间平行的物种形成过程。寄生虫与寄主之间通常有很紧密的关系,它们无法离开寄主太久,终身生活于寄主身上或体内;而且有高度专一性,一种寄生虫只寄生于某种
  • 东岳殿台南东岳殿,是位于台南市中西区的东岳庙,主祀东岳仁圣大帝,俗称岳帝庙,或作岳帝庙,创建于明郑时期,为台湾最早奉祀东岳仁圣大帝之首庙,亦为昔日台湾府城七寺八庙、府城八协境庙宇之
  • 小分子核糖核酸小分子核糖核酸(英语:microRNA,缩写为miRNA)又译微核糖核酸,是真核生物中广泛存在的一种长约21到23个核苷酸的核糖核酸(RNA)分子,可调节其他基因的表达。miRNA来自一些从DNA转录而来
  • 李埏李埏(1914年11月21日-2008年5月12日),字子泝,号幼舟,彝族,出生于云南省路南县,中国历史学家、云南大学历史系教授。李埏是中国土地所有制研究的重要代表,在货币经济史、唐宋经济史、
  • 尚武文化尚武文化, 以武力技术、知识等作为保卫、进攻、杀伤、掠夺等诸攻防行动作战方式的文化。正面观点:有助于抗御外敌或有效击败危及已方或友邻时的保卫手段,达到克敌制胜之道。反