贝齐埃曲线德卡斯特里奥(de Casteljau)算法及程序

王朝vc·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

贝齐埃曲线德卡斯特里奥(de Casteljau)算法及程序

1) 描述

de Casteljau算法最基本的概念就是在线段AB中找到C点,使得C点将AB线段划分成u:(1-u)比例(|AC|:|AB|=u),怎么找这个C点呢?

A 到 B 的向量是 B – A ,因为u在0到1之间,所以C点就在u(B – A)处,考虑到A点的位置,C点的位置是A + u(B – A) = (1 – u)A + uB,因此,对于一个给定的u,(1–u)A + uB就是在A 和 B之间的C点,C点将AB线段划分成u:(1–u)比例。

de Casteljau算法的思想如下面所述:假设我们要求C(u),其中u 在 [0,1]之间,从第一个多边开始,00-01-02-03...-0n,用上面的公式求得一个在0i 到0(i+1)的线段上的点1i,1i点将0i 到0(i+1)的线段划分成u:(1–u)比例;这样我们可以得到n 个点10, 11, 12, ...., 1(n-1),它们形成了新的n–1条线段。

上图中,u = 0.4,10 是00 到01线段上的点,11是01到02线段上的点,…,14是04到05线段上的点,所有的新点是兰色显示的。

新点按1i方式命名,对这些新点执行相同的操作,我们将可以得到第二个由(20, 21,…,2(n-2))n–1个点组成的多边和n–2条边;再次进行该操作,我们将可以得到第三个由(30, 31,…,3(n-3))n–2个点组成的多边和n–3条边;如此循环进行n次后,将产生一个单点n0;de Casteljau证明这个点就是我们要求的C(u)。

让我们继续看上面的图形,得到10 到11的线段上的点20将10 到11的线段划分成u:(1–u)比例,同样可以得到11 到12的线段上的点21,12 到13的线段上的点22,13 到14的线段上的点23,这第三个多边有四个点和三条边;如此继续,我们可以得到由30, 31 和 32三个点组成的新多边;再从这第四个多边,我们可以得到由40 和41 两个点组成的第五个多边;如此再进行一次,我们可以得到50, 这就是曲线上我们要求的C(u)。

这就是de Casteljau算法的几何解释,非常美妙的曲线设计。

注:以上原文出自

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/Bezier/de-casteljau.html

2) 程序

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// pDC 设备

// flArrayx 组成点x坐标序列

// flArrayy 组成点y坐标序列

//created by: handwolf

//create time: 2004-10-1

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int deCasteljau(CDC *pDC,CArray<float,float>& flArrayx,CArray<float,float>& flArrayy)

{

if(flArrayx.GetSize()!=flArrayy.GetSize())

return 0;

float *pflX,*pflY;

float flTempx,flTempy,flU;//flu-------u参数

int i,n,j;

n=flArrayx.GetSize();

if(n<2) return 0;

pflX=new float[n];

pflY=new float[n];

flTempx=flArrayx.GetAt(0);

flTempy=flArrayy.GetAt(0);

for(i=0;i<n;i++){

pflX[i]=flArrayx.GetAt(i);

pflY[i]=flArrayy.GetAt(i);

}

for(flU=0;flU<=1;flU+=0.05/n){

for(i=1;i<n;i++){

for(j=0;j<n-i;j++){

pflX[j]=(1-flU)*pflX[j]+flU*pflX[j+1];

pflY[j]=(1-flU)*pflY[j]+flU*pflY[j+1];

}

}

pDC->MoveTo(flTempx,flTempy);

pDC->LineTo(pflX[0],pflY[0]);

flTempx=pflX[0];

flTempy=pflY[0];

}

delete[] pflX;

delete[] pflY;

return 1;

}

////////////////////////////////////////////////////结束//////////////////////////////////////////////////////////////////////////

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有  導航