知道曲线p1 p2 p3 pi ... pn,求一曲线通过这些点的算法 200分速

贝兹曲线吧？
http://topic.csdn.net/t/20021223/15/1291855.html
http://www.picai8.com/soft/softInfo/34801.html

就是 Bezier 曲线Bezier曲线定义：
　　给定n+1个控制顶点Pi(i=0~n) ，则Bezier曲线定义为：
　　P(t)=∑Bi,n(t)Pi t∈[0,1]
　　其中：Bi,n(t)称为基函数。
　　Bi,n(t)=Ci nti (1-t)n-i
　　Ci n=n!/(i!*(n-i)!)

1楼说的和我要的不一样。感谢！补充：GDI+ 里面有个Graphics::DrawCurve 的函数可以绘制这种曲线，现在我需要的是从X轴的开始到结束的每个X所对应的Y值（就是在这个曲线上面的所有点的坐标）。
GDI+ 里面只有绘制可是没有提供求这一串坐标的函数，而我需要的是在这个曲线里面的所有的点。

2楼，bezier需要一些控制点，而我没有控制点，有的是曲线得经过的一些点。
可能是bezier的逆过程。

GDI+ 里面把这个曲线叫做 cardinal spline。
或许叫法样式有很多种。

多项式函数拟合：a=polyfit(xdata,ydata,n)
其中n表示多项式的最高阶数，xdata，ydata为将要拟合的数据，它是用数组的方式输入．输出参数a为拟合多项式的系数
多项式在x处的值y可用下面程序计算．y=polyval(a,x)
一般的曲线拟合：p=curvefit(‘Fun’,p0,xdata,ydata)

amei2000go 谢谢，我看看先。
在Codeproject看到一个埃及人说的拉格朗日公式也可以做这个，开始他的demo做的有问题，点的位置好像有特殊的要求。

呵，不能所有的点，就是整数点吧因为pi 到 pn 最多几百个点吧amei2000go 你的那些公式有没有code啊，那几个函数不是什么库的函数吧。

biweilun  也来了  上次回复你后，你就没有到我帖子来了  所有还有不清楚的地方，而且上次可能问题没有说清楚。
p(f)= v3*f^3+v2*3*f^2*(1-f)+v1*3*f*(1-f)^2+v0*(1-f)^3  我有的不是控制点，而是曲线经过的一些点，需要根据曲线经过的一些点来求得曲线上面的其余的点（X1 到 Xn 中间的N-1个点的坐标）
你看一下上次的公式还能套用吗？还用，上次的那个公式看起来需要使用逼近的方法，是否速度上会慢一点？

to biweilun :p(f)= v3*f^3+v2*3*f^2*(1-f)+v1*3*f*(1-f)^2+v0*(1-f)^3
这个公式是关于f的，可是点坐标都是Ｘ、Ｙ的。
是否X、Y公式都一样的。把上面的V都用X代入或者Y代入从而求出f可是求出f后，还是不能理解到怎么去求得X-Y的对应函数映射啊

bezier曲线是一种参数曲线，也就是说，是很难找到关于X、Y关系的方程的，次数高了以后，根本不要妄图去找这样的方程，曲线只能由一个参数方程决定，比如t,一条曲线，就是t从0到1变化过程中所有的(X(t)，Y(t))组成的。楼主的问题如果选用bezier曲线，那么实际上应该先从曲线通过P0~Pn这个条件找出bezier控制点C0~Cn,然后再从bezier曲线定义出发找到曲线上的每个点。第一步看上去比较复杂，实际也很简单，C0=P0, Cn=Pn，对于中间每个Pi, 认为ti = i/n。然后带入2楼给的方程组P(t)=∑Bi,n(t)Pi t∈[0,1]
会得到一个n-1个未知数，n-1个方程的线性方程组，x,y方向是两个独立的方程组，解出来就是C1~Cn-1。这样就得到了所有的n+1个控制点。第二步就更简单了，对t设一个步长，比如0.01或者0.001。从0到1一突突，就得到100或者1000个点，想画的话，把这些点用直线段连起来就是了，中间的点可以线性插值，对我们工程师来说，根本算不上什么误差。

x = [1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160];
y = [56
393
1075
2110
3508
5283
7448
10016
13003
16426
20298
24641
29470
34806
40668
47077
54055
61624
69806
78627
88112
98286
109175
120809
133217
146425
160467
175374
191180
207918
225624
244330
264082
284912
306863
329973
354291
379857
406715
434912
464505
495535
528054
562114
597784
635104
674140
714939
757597
802142
848657
897208
947849
1000694
1055780
1113192
1172994
1235322
1300208
1367754
1438020
1511182
1587246
1666352
1748560
1834054
1922874
2015140
2110940
2210484
2313800
2421036
2532276
2647792
2767576
2891816
3020640
3154156
3292672
3436188
3584912
3738904
3898608
4063952
4235160
4412376
4596032
4786032
4982712
5186144
5396864
5614744
5840200
6073176
6314480
6563840
6821648
7088080
7363776
7648624
7942976
8247200
8561296
8886288
9221760
9568352
9926048
10295984
10677744
11071904
11478688
11899104
12332864
12780608
13242368
13719552
14211680
14719520
15242976
15784032
16341504
16916768
17509536
18121856
18753024
19403584
20074720
20765856
21479744
22215040
22973120
23753728
24559744
25389824
26245248
27125824
28035008
28980580
29925596
30927744
31952320
33006592
34092608
35210240
36363264
37550208
38771968
40029184
41326336
42660608
44034432
45448960
46903424
48404224
49947264
51535872
53169024
54853760
56585600
58368512];[a S] = polyfit(x, y, 6);
xx = 1:0.5:160;
es_y = polyval(a,xx);
plot(xx,es_y,'r')这是我以前用 matlab 模拟一些连续点的多项式代码

amei2000go 呵呵，给结果不行啊，需要过程。还好，根据大家给的信息，和自己找的一些东西，前两天完成了这个模块了。
由于比较忙一点，所以结贴慢了，见谅。
其实就是曲线拟合，然后是插值，每几个点就插n个点，一般人是n=100，不过可以根据点和点之间的距离调整。
算法比较多，样条、抛物线等。感谢大家。

我正好在做这块，我采用的是三次样条插值，通过验证后插值效果非常好！源代码附下，楼主只需使用即可！楼主上面的问题太笼统，插值算法有好多种：牛顿插值，拉格朗日插值，这些是稍微简单的，然后贝塞尔插值，三次样条插值这些相对复杂的！三次样条插值一般用在给定几个点，求一流水型的曲线过这几个点，通俗的将就是柳条法！代码附下！直接调用即可，有什么问题再联系！
/***********三次样条插值函数*****************************/
typedef enum _condition
{//边界条件
    NATURAL,//自然边界
    CLAMPED,//夹持边界
    NOTaKNOT//非扭结边界
}condition;typedef struct _coefficient
{//对应每个区间段的基函数对应的系数
    double a3;
    double b2;
    double c1;
    double d0;
}coefficient;typedef struct _splinePoint
{
    coefficient *coe;//存储两点间多项式系数
    double *xCoordinate;//被插值值对应(x,y)坐标
    double *yCoordinate;
    int num;//对应插值坐标点数    double f0;//对应区间的边界条件
    double fn;    condition con;//何种边界条件
}splinePoint;
int Spline(splinePoint *point);
void GetSplineData(::splinePoint p,double* inX,double* inY,int inSize,double* outX,double* outY,int outSize);//给原始点，得出插入点
/*********三次样条插值函数******************************/int Spline(splinePoint *point)
{//三次样条插值
    double *x = (*point).xCoordinate;
double *y = (*point).yCoordinate;
    int n = (*point).num - 1;
    coefficient *coe = (*point).coe;
    condition con = (*point).con;
    double *h, *d;
double *a, *b, *c, *f, *m;
    double temp;
    int i;
    h = (double *)malloc( n * sizeof(double) ); /* 0,1--(n-1),n */
    d = (double *)malloc( n * sizeof(double) ); /* 0,1--(n-1),n */

    a = (double *)malloc( (n + 1) * sizeof(double) ); /* 特别使用,1--(n-1),       n */
    b = (double *)malloc( (n + 1) * sizeof(double) ); /*        0,1--(n-1),       n */
    c = (double *)malloc( (n + 1) * sizeof(double) ); /*        0,1--(n-1),特别使用 */
    f = (double *)malloc( (n + 1) * sizeof(double) ); /*        0,1--(n-1),       n */
    m = b;
    if(f == NULL)
    {
        free(h);
        free(d);
        free(a);
        free(b);
        free(c);
        return 1;
    }
    /* 计算 h[] d[] */
    for (i = 0; i < n; i++)
    {
        h[i] = x[i + 1] - x[i]; //存储每段之间的h值
        d[i] = (y[i + 1] - y[i]) / h[i];//d[i]表示点的导数，除去最后一个点
    }    /**********************
    ** 初始化系数增广矩阵
    **********************/
    a[0] = (*point).f0;//置零
    c[n] = (*point).fn;
    /* 计算 a[] b[] d[] f[] */
    switch(con)
    {
        case NATURAL://自然边界
            f[0] = a[0];//边界为零
            f[n] = c[n];            a[0] = 0;
            c[n] = 0;            c[0] = 0;
            a[n] = 0;            b[0] = 1;
            b[n] = 1;
        break;

        case CLAMPED://夹持边界
            f[0] = 6 * (d[0] - a[0]);
            f[n] = 6 * (c[n] - d[n - 1]);            a[0] = 0;
            c[n] = 0;            c[0] = h[0];
            a[n] = h[n - 1];            b[0] = 2 * h[0];
            b[n] = 2 * h[n - 1];
        break;

        case NOTaKNOT://非扭结边界
            f[0] = 0;
            f[n] = 0;            a[0] = h[0];
            c[n] = h[n - 1];            c[0] = -(h[0] + h[1]);
            a[n] = -(h[n - 2] + h[n - 1]);            b[0] = h[1];
            b[n] = h[n - 2];
        break;
    }    for (i = 1; i < n; i++)
    {
        a[i] = h[i - 1];//存放x段的距离
        b[i] = 2 * (h[i - 1] + h[i]);
        c[i] = h[i];
        f[i] = 6 * (d[i] - d[i - 1]);
    }
    /* for (i = 0; i < n+1; i++)   printf("%f\n", c[i]); */

    /*************
    ** 高斯消元
    *************/
    /* 第0行到第(n-3)行的消元 */
    for(i = 0; i <= n - 3; i++)
    {
        /* 选主元 */
        if( fabs(a[i + 1]) > fabs(b[i]) )
        {
            temp = a[i + 1]; a[i + 1] = b[i]; b[i] = temp;//a[i + 1]与b[i]对换
            temp = b[i + 1]; b[i + 1] = c[i]; c[i] = temp;//b[i + 1]与c[i]对换
            temp = c[i + 1]; c[i + 1] = a[i]; a[i] = temp;//c[i + 1]与a[i]对换
            temp = f[i + 1]; f[i + 1] = f[i]; f[i] = temp;//f[i + 1]与f[i]对换
        }
        temp = a[i + 1] / b[i];
        a[i + 1] = 0;
        b[i + 1] = b[i + 1] - temp * c[i];
        c[i + 1] = c[i + 1] - temp * a[i];
        f[i + 1] = f[i + 1] - temp * f[i];
    }

    /* 最后3行的消元 */
    /* 选主元 */
    if( fabs(a[n - 1]) > fabs(b[n - 2]) )
    {
        temp = a[n - 1]; a[n - 1] = b[n - 2]; b[n - 2] = temp;
        temp = b[n - 1]; b[n - 1] = c[n - 2]; c[n - 2] = temp;
        temp = c[n - 1]; c[n - 1] = a[n - 2]; a[n - 2] = temp;
        temp = f[n - 1]; f[n - 1] = f[n - 2]; f[n - 2] = temp;
    }
    /* 选主元 */
    if( fabs(c[n]) > fabs(b[n - 2]) )
    {
        temp = c[n]; c[n] = b[n - 2]; b[n - 2] = temp;
        temp = a[n]; a[n] = c[n - 2]; c[n - 2] = temp;
        temp = b[n]; b[n] = a[n - 2]; a[n - 2] = temp;
        temp = f[n]; f[n] = f[n - 2]; f[n - 2] = temp;
    }
    /* 第(n-1)行消元 */
    temp = a[n - 1] / b[n - 2];
    a[n - 1] = 0;
    b[n - 1] = b[n - 1] - temp * c[n - 2];
    c[n - 1] = c[n - 1] - temp * a[n - 2];
    f[n - 1] = f[n - 1] - temp * f[n - 2];
    /* 第n行消元 */
    temp = c[n] / b[n - 2];
    c[n] = 0;
    a[n] = a[n] - temp * c[n - 2];
    b[n] = b[n] - temp * a[n - 2];
    f[n] = f[n] - temp * f[n - 2];
    /* 选主元 */
    if( fabs(a[n]) > fabs(b[n - 1]) )
    {
        temp = a[n]; a[n] = b[n - 1]; b[n - 1] = temp;
        temp = b[n]; b[n] = c[n - 1]; c[n - 1] = temp;
        temp = f[n]; f[n] = f[n - 1]; f[n - 1] = temp;
    }
    /* 最后一次消元 */
    temp = a[n] / b[n-1];
    a[n] = 0;
    b[n] = b[n] - temp * c[n - 1];
    f[n] = f[n] - temp * f[n - 1];

    /* 回代求解 m[] */
    m[n] = f[n] / b[n];
    m[n - 1] = (f[n - 1] - c[n - 1] * m[n]) / b[n-1];
    for(i = n - 2; i >= 0; i--)
    {
        m[i] = ( f[i] - (m[i + 2] * a[i] + m[i + 1] * c[i]) ) / b[i];
printf("%f",m[i]);
// printf("\n");
    }
    /* for (i = 0; i < n+1; i++)   printf("%f\n", m[i]); */
    free(a);
    free(c);
    free(f);
    /************
    ** 放置参数
    ************/
//                Y(j+1) - Yj    ( 2*Mj + M(j+1) )                   Mj              M(j+1) - Mj
//Sj(x) = Yj + [ ------------- - -----------------*Hj ]*( x - Xj) + ----(x - Xj)^2 + ------------(x - Xj)^3
//                    Hj               6                              2                 6Hj
//
//Hj = X(j+1) - Xj   x属于[ Xj , X(j+1) ],j = ( 0 , 1 , 2 ,...,n-1 )
//
//
//a3,b2,c1,d0分别对应三次基函数，二次基函数，一次基函数，零次基函数的系数，直接代入即可。注意各段区间内使用的系数
//
//
    for(i = 0; i < n; i++)
    {
        coe[i].a3 = (m[i + 1] - m[i]) / (6 * h[i]);
        coe[i].b2 = m[i] / 2;
        coe[i].c1 = d[i] - (h[i] / 6) * (2 * m[i] + m[i + 1]);//d[i] = (y[i + 1] - y[i]) / h[i]
        coe[i].d0 = y[i];
    }

    free(h);
    free(d);
    free(b);
    return n + 1;
}

调试易

知道曲线p1 p2 p3 pi ... pn,求一曲线通过这些点的算法 200分速

解决方案 »

知道曲线p1 p2 p3 pi ... pn,求一曲线通过这些点的算法 200分 速

解决方案 »

知道曲线p1 p2 p3 pi ... pn,求一曲线通过这些点的算法 200分速