德卡斯特里奥算法

✍ dations ◷ 2025-07-23 22:51:13 #算法,数值分析,样条

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

(该代码用到)

相关

  • 发电厂发电厂(英语:Power station、Generating station、Power plant、Powerhouse),又称发电站或电厂,是将热能或动能转换为电能的设施,属于电力系统一环。根据原动机的不同来分类有:其中
  • 埃及神话埃及神话指源自古埃及的一系列神话。通过描绘众多神明,古埃及人得以更好地理解当时的整个世界,这些神话故事也是古埃及宗教的重要组成部分。埃及神话在古埃及文学和艺术作品中
  • 德意志民主共和国德意志民主共和国(德语:Deutsche Demokratische Republik;英语:German Democratic Republic),简称民主德国(德语:DDR;英语:GDR)、东德(East Germany)或民德,是存在于1949年至1990年的中欧
  • 女排银牌得主1984年夏季奥林匹克运动会的排球项目只有两个小项,共产出两面金牌;排球项目于1984年7月29日至8月10日进行。本届排球比赛设有两个比赛项目,包括:
  • 英国自治领自治领(英语:Dominion)是大英帝国殖民地制度下一个特殊的国家体制,可说是殖民地步向独立的最后一步。19世纪,所有实行自治或半自治的英国殖民地,尤其那些已具有自身宪政体制的,如加
  • 因提夫二世因提夫二世(Intef II)埃及第十一王朝(约公元2081年∼约公元前1939年)第三代国王。在其长久的统治时期,曾与埃及第九和第十王朝中埃及和下埃及(即埃及北部)的统治者赫拉克来俄波利斯
  • 小人物大英雄《无名英雄》(英文:)是一部在1992年上映的美国喜剧电影,由史蒂芬佛瑞尔斯执导,达斯汀霍夫曼、吉娜黛维丝、安迪嘉西亚等人主演。一名犯重罪被通缉的流浪汉伯尼拉普兰 Bernie Lapl
  • 高名凯高名凯(1911年3月28日-1965年1月3日),男,福建平潭人。中国语言学家,汉语语法学家,文学翻译家。1911年3月28日生于福建省平潭县苏澳区先进乡土库村。7岁入私塾读书,10岁入平潭开宗小
  • 翁史烈翁史烈(1932年5月21日-),热机专家,原上海交通大学校长,中国工程院院士(1995年当选)1932年出生于浙江省宁波。1952年毕业于交通大学造船系。1962年毕业于苏联列宁格勒造船学院,获副博
  • 姚汝循姚汝循(1535年-1597年),字叙卿,浙江金华府永康县人,南京锦衣卫籍,明朝政治人物。应天府乡试第五十九名举人。嘉靖三十五年(1556年)中式丙辰科三甲第六十四名进士。官大名府知府,后罢官