图形中点之间连接的曲线算法

Question

我需要开发一种算法，以平滑曲线的方式连接点，即非线性连接，如下图所示：

问题是我找不到最好的解决方案，无论是使用Bezier曲线，多项式插值，曲线调整等方法。

简而言之，我需要一个公式，根据上图插值点，生成N个坐标之间的中间点。

在上面的图片中，第一个坐标（c1）是（x = 1，y = 220），第二个坐标（c2）是（x = 2，y = 40）。

因此，如果我想在c1和c2之间创建4个中间坐标，我将得到一个类似于以下内容的4个元素的数组（x，y）：

    

[1.2, 180], [1.4, 140], [1.6, 120], [1.8, 80]

有人有什么想法吗？

- Rogério Dec

---

你没有说其他尝试有什么问题，但是在我看来，这似乎是一个单变量的三次样条插值。参见：http://mathworld.wolfram.com/CubicSpline.html...不过，在6和7之间的拐点似乎不自然。 - Matt Timmermans

@MattTimmermans 这很可能是因为起始和结束控制点不可见... - Spektre

任何三次插值都可以胜任，例如像这样：分段曲线插值。 - Spektre

@Matt Timmermans和@Spektre，谢谢你们，但我认为我比你们的知识落后了几步。我不是数学家，也不熟悉高级公式。对于我来说，更容易理解的是看到任何工作语言的代码，以便逐步理解。你们能帮我吗？例如，在我上面提到的例子中，在已知的前两个点（x = 1和x = 2）之间，当x等于1.2、1.4等时，我该如何计算y？ - Rogério Dec

如果你的点像你发布的图片一样均匀分布，那么我在这里展示了一种Python的简单方法：http://nbviewer.jupyter.org/github/mtimmerm/IPythonNotebooks/blob/master/NaturalCubicSplines.ipynb - Matt Timmermans

Answer 1

我认为任何分段曲线插值方法都可以胜任。这里有一个小的C++示例：

Piecewise curve interpolation

//---------------------------------------------------------------------------
const int n=7;      // points
const int n2=n+n;
float pnt[n2]=      // points x,y ...
    {
    1.0, 220.0,
    2.0,  40.0,
    3.0,-130.0,
    4.0,-170.0,
    5.0,- 40.0,
    6.0,  90.0,
    7.0, 110.0,
    };
//---------------------------------------------------------------------------
void getpnt(float *p,float t)   // t = <0,n-1>
    {
    int i,ii;
    float *p0,*p1,*p2,*p3,a0,a1,a2,a3,d1,d2,tt,ttt;
    // handle t out of range
    if (t<=      0.0f){ p[0]=pnt[0]; p[1]=pnt[1]; return; }
    if (t>=float(n-1)){ p[0]=pnt[n2-2]; p[1]=pnt[n2-1]; return; }
    // select patch
    i=floor(t);             // start point of patch
    t-=i;                   // parameter <0,1>
    i<<=1; tt=t*t; ttt=tt*t;
    // control points
    ii=i-2; if (ii<0) ii=0; if (ii>=n2) ii=n2-2; p0=pnt+ii;
    ii=i  ; if (ii<0) ii=0; if (ii>=n2) ii=n2-2; p1=pnt+ii;
    ii=i+2; if (ii<0) ii=0; if (ii>=n2) ii=n2-2; p2=pnt+ii;
    ii=i+4; if (ii<0) ii=0; if (ii>=n2) ii=n2-2; p3=pnt+ii;
    // loop all dimensions
    for (i=0;i<2;i++)
        {
        // compute polynomial coeficients
        d1=0.5*(p2[i]-p0[i]);
        d2=0.5*(p3[i]-p1[i]);
        a0=p1[i];
        a1=d1;
        a2=(3.0*(p2[i]-p1[i]))-(2.0*d1)-d2;
        a3=d1+d2+(2.0*(-p2[i]+p1[i]));
        // compute point coordinate
        p[i]=a0+(a1*t)+(a2*tt)+(a3*ttt);
        }
    }
//---------------------------------------------------------------------------
void gl_draw()
    {
    glClearColor(1.0,1.0,1.0,1.0);
    glClear(GL_COLOR_BUFFER_BIT);
    glDisable(GL_DEPTH_TEST);
    glDisable(GL_TEXTURE_2D);

    // set 2D view 
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();
    glScalef(1.0/5.0,1.0/500.0,1.0);
    glTranslatef(-4.0,0.0,0.0);

    // render lines
    glColor3f(1.0,0.0,0.0);
    glBegin(GL_LINE_STRIP);
    float p[2],t;
    for (t=0.0;t<=float(n-1);t+=0.1f)
        {
        getpnt(p,t);
        glVertex2fv(p);
        }
    glEnd();

    // render points
    glPointSize(4.0);
    glColor3f(0.0,0.0,1.0);
    glBegin(GL_POINTS);
    for (int i=0;i<n2;i+=2) glVertex2fv(pnt+i);
    glEnd();
    glPointSize(1.0);

    glFinish();
    SwapBuffers(hdc);
    }
//---------------------------------------------------------------------------

这里是预览：

如您所见，它很简单，您只需要n个控制点pnt（我从您的图表中提取）并进行插值...getpnt函数将计算由参数t=<0,n-1>表示的曲线上的任何点。在内部，它只是选择要使用的三次补丁并计算为单个三次曲线。在gl_draw中，您可以看到如何使用它来获得中间点。

由于您的控制点在x轴上均匀分布：

x = <1,7>
t = <0,6>

我可以写：

x = t+1
t = x-1

这样你就可以计算任何点的任何x值了...

由于所选的控制点不正确，因此该形状与您的图形并不完全匹配。任何局部最小值/最大值都应该是一个控制点，有时还可以使用反曲点。曲线的起始和结束形状暗示了隐藏的起始和结束控制点，在图形上没有显示出来。您可以使用任意数量的点，但要注意，如果打破x均匀分布，那么您将失去直接从x计算t的能力！

由于我们不知道图表是如何创建的，所以我们只能猜测...

- Spektre

---

抱歉我回复晚了。这很完美！非常感谢您的工作和支持！ - Rogério Dec