贝齐埃曲线德卡斯特里奥（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;
}
////////////////////////////////////////////////////结束////////////////////////////////////////////////////////////////////////// 
|
本类阅读TOP10