贝齐埃曲线德卡斯特里奥（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;

}

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