用三次样条插值拟合光滑曲线的问题

Question

小弟最近遇到这个问题：给定一组曲线经过的点的坐标，求经过这些点的平滑曲线的Bezier曲线控制点。我的想法是：先用三次样条插值拟合出曲线，然后反求任意两点之间的Bezier控制点。现在问题是，三次样条插值算法，偶从来没用过，在网上看了看资料也看得迷糊，那些代码变量命名简直看不明白。哪位大侠给给清晰点的代码，或者简单讲下原理，在下感激不尽！

Answer 1

//三次样条插值函数
double GetValueSpline(int n, double x[], double y[], double t)
{ 
    int i,j;
    double h0,h1,alpha,beta,*s,z,*dy;
    dy=new double[n];
    for(i=0;i<n;i++)dy[i]=0.0;
    // 初值
    s=new double[n];
    s[0]=dy[0]; 
    dy[0]=0.0;
    h0=x[1]-x[0];
    
    for (j=1;j<=n-2;j++)
    { 
        h1=x[j+1]-x[j];
        alpha=h0/(h0+h1);
        beta=(1.0-alpha)*(y[j]-y[j-1])/h0;
        beta=3.0*(beta+alpha*(y[j+1]-y[j])/h1);
        dy[j]=-alpha/(2.0+(1.0-alpha)*dy[j-1]);
        s[j]=(beta-(1.0-alpha)*s[j-1]);
        s[j]=s[j]/(2.0+(1.0-alpha)*dy[j-1]);
        h0=h1;
    }    for (j=n-2;j>=0;j--)dy[j]=dy[j]*dy[j+1]+s[j];
    
    for (j=0;j<=n-2;j++)s[j]=x[j+1]-x[j];
    
    if (t>=x[n-1])i=n-2;
    else
    { 
        i=0;
        while (t>x[i+1]) 
        i=i+1;
    }
        
    h1=(x[i+1]-t)/s[i];
    h0=h1*h1;
    z=(3.0*h0-2.0*h0*h1)*y[i];
    z=z+s[i]*(h0-h0*h1)*dy[i];    h1=(t-x[i])/s[i];
    h0=h1*h1;
    z=z+(3.0*h0-2.0*h0*h1)*y[i+1];
    z=z-s[i]*(h0-h0*h1)*dy[i+1];
    
    delete[] s;
    delete[] dy;    return(z);
}
实际上就是一个追赶法解线型方程组

Answer 2

2楼老大，我在您的blog里也发现了这段代码，但是还是不太明白，我该怎么用呢？
我要做的目标是实现类似GDI+中的GraphicsPath类的AddCurve方法，
即给定一组点，生成经过这些点的Bezier曲线的控制点。
即：如给定(50.0, 50.0), (60.0, 20.0)
声成的Bezier控制点如下：
起始点就是第一个了，然后有(53.333333, 40.0), (53.333333, 3.3333333), 然后是结束点。
当然，这是最简单的2个点的情况。

Answer 3

5楼大哥，我发现你所说的问题了，
这样就会出现如果给的点x值小于前面的点的话，就会有问题。
那这个目标应该到底怎么实现呢？：即给定一组点，生成经过这些点的Bezier曲线的控制点。
即：如给定(50.0, 50.0), (60.0, 20.0)
声成的Bezier控制点如下：
起始点就是第一个了，然后有(53.333333, 40.0), (53.333333, 3.3333333), 然后是结束点。
也即每两个点之间都有2个bezier控制点，
现在首先要拟合出曲线，但是又该怎么拟合呢？三次插值好象不行，老大门，还有其他的办法吗？这里还要说下的是，AddCurve还有一个参数 mention, 这个值可以用来确定曲线的张力或者长度。该值不同，生成的曲线的控制点也不同。

Answer 4

生成经过这些点一般不经过Bezier曲线的控制点
控制点需要另外的求法，很多书上都有

Answer 5

生成经过这些点一般不经过Bezier曲线的控制点（除首尾外）

Answer 6

我的意思是先拟合出曲线，然后反求出其Bezier控制点。
现在三次样条插值好象存在一些不足，对椭圆等曲线不能很好拟合呀

Answer 7

Bezier也不能很好的拟合
用非均匀有理B样条才能精确的拟合

Answer 8

一叶樟目 大哥，现在就是缺乏一个好的拟合的算法，只要能拟合出来曲线上2点之间的其他2点，应该就可以求出其Bezier控制点了。
老大，可否给个代码？

Answer 9

现在问题是，三次样条插值，可以用Catmull－Rom插值算法，
http://www.mvps.org/directx/articles/catmull/
参考代码：
void CCatmullDlg::CatmullRom(POINT* pIn,float t,POINT* pOut)
{
float t1,t2,t3;
t2=t*t;
t3=t*t*t;
t1=(1-t)*(1-t); pOut->x=(-t*t1*pIn[0].x+(2-5*t2+3*t3)*pIn[1].x+t*(1+4*t-3*t2)*pIn[2].x-t2*(1-t)*pIn[3].x)/2;
pOut->y=(-t*t1*pIn[0].y+(2-5*t2+3*t3)*pIn[1].y+t*(1+4*t-3*t2)*pIn[2].y-t2*(1-t)*pIn[3].y)/2;
}

Answer 10

其中：
pIn必须为四个成员的数组。