平滑的希尔伯特曲线

Question

我正在尝试平滑Hilbert curve所经过的路径。我可以定义点并通过直线连接它们，但我想要一条不那么急转弯的路径。我尝试使用越来越高阶的贝塞尔曲线连接曲线，但这并不起作用，当我尝试重新连接它们时，路径上总是有“折痕”:

我觉得这是一个已经解决的问题，但我没有搜索到正确的术语。

- Hooked

---

你如何定义曲线中应包含哪些点以及要丢弃哪些点？连接所有点的平滑曲线可能会自交。 - meowgoesthedog

@meowgoesthedog 很好的问题，但我不需要它完全符合所有要点，而是接近它们，并且流畅。 - Hooked

这里不是使用一个贝塞尔曲线，而是将多个贝塞尔曲线（每个曲线有四个控制点）拼接在一起。你需要的是样条曲线（可能是B样条）。 - Nico Schertler

你刚刚错误地连接了高阶曲线，这样做不会有任何帮助，反而会导致自交问题。为此，请坚持使用4点三次样条，并以分段方式进行...请查看我的回答（特别是计算 p0，p1，p2，p3 点的部分）和其中的链接。 - Spektre

@Hooked 我尝试在这里实现了3D效果 将希尔伯特值映射到3D点 这是结果（也去掉了2D的海龟图形） - Spektre

Answer 1

如何使用分段三次曲线来实现这个...无论是贝塞尔样条还是其他的都不太重要。你只需要用正确的点调用顺序连接补丁，而你显然没有这样做。这是我的示例，使用我的插值三次曲线和正确的调用顺序：

灰色是乌龟图形原始的希尔伯特曲线，水绿色是相同点的插值三次曲线...

我很好奇，所以想要实现这个，但我花了一段时间才弄清楚并实现了2D希尔伯特曲线（我使用了乌龟图形），因为我以前从未使用过它们。这里是此代码的OpenGL VCL C++源代码:

//---------------------------------------------------------------------------
double ha=0.0; AnsiString hs="";    // turtle graphics
List<double> pnt;                   // 2D point list
//---------------------------------------------------------------------------
void turtle_mirror(AnsiString &s)   // swap l,r
    {
    int i,l; char c;
    for (l=s.Length(),i=1;i<=l;i++)
        {
        c=s[i];
        if (c=='l') s[i]='r';
        if (c=='r') s[i]='l';
        }
    }
//---------------------------------------------------------------------------
void turtle_hilbert(AnsiString &s,double &a,int n)  // compute hilbert curve turtle string s , line segment size a for n iterations
    {
    int i,l; char c;
    AnsiString s0;
    if (s=="") { l=1; s="frfrf"; }  // init hilbert curve assuming starting bottom left turned up
    for (i=0;i<n;i++)
        {
        s0=s;                   // generator
        if (int(i&1)==0)        // even pass
            {
            turtle_mirror(s0); s ="r"+s0+"rf";
            turtle_mirror(s0); s+=s0+"lfl"+s0;
            turtle_mirror(s0); s+="fr"+s0;
            }
        else{                   // odd pass
            turtle_mirror(s0); s ="r"+s0+"f";
            turtle_mirror(s0); s+=s0+"fl"+s0;
            turtle_mirror(s0); s+="rfr"+s0;
            }
        l=l+l+1;                // adjust scale
        }
    a=1.0/double(l);
    }
//---------------------------------------------------------------------------
void turtle_draw(double x,double y,double dx,double dy,const AnsiString &s)
    {
    int i,l; char c;
    double q;
    l=s.Length();
    glBegin(GL_LINE_STRIP);
    glVertex2d(x,y);
    for (i=1;i<=l;i++)
        {
        c=s[i];
        if (c=='f') { x+=dx; y+=dy; glVertex2d(x,y); }
        if (c=='l') { q=dx; dx=-dy; dy= q; }
        if (c=='r') { q=dx; dx= dy; dy=-q; }
        }
    glEnd();
    }
//---------------------------------------------------------------------------
void turtle_compute(List<double> &xy,double x,double y,double dx,double dy,const AnsiString &s)
    {
    int i,l; char c;
    double q;
    l=s.Length();
    xy.num=0;   // clear list
    xy.add(x);  // add point
    xy.add(y);
    for (i=1;i<=l;i++)
        {
        c=s[i];
        if (c=='f') { x+=dx; y+=dy; xy.add(x); xy.add(y); }
        if (c=='l') { q=dx; dx=-dy; dy= q; }
        if (c=='r') { q=dx; dx= dy; dy=-q; }
        }
    glEnd();
    }
//---------------------------------------------------------------------------
void gl_draw()
    {
    //_redraw=false;
    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

    GLint id;
    glUseProgram(prog_id);

    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    glMatrixMode(GL_TEXTURE);
    glLoadIdentity();
    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();

    glDisable(GL_DEPTH_TEST);
    glDisable(GL_TEXTURE_2D);

    // hilber curve covering <-1,+1> range
    if (hs=="")
        {
        turtle_hilbert(hs,ha,3);                        // init turtle string
        turtle_compute(pnt,-0.9,-0.9,0.0,1.8*ha,hs);    // init point list for curve fit
        }
    // render hs,ha as turtle graphics
    glColor3f(0.4,0.4,0.4);
    turtle_draw(-0.9,-0.9,0.0,1.8*ha,hs);
    // render pnt[] as interpolation cubics
    int i,j;
    double  d1,d2,t,tt,ttt,*p0,*p1,*p2,*p3,a0[2],a1[2],a2[2],a3[2],p[2];
    glColor3f(0.2,0.7,1.0);
    glBegin(GL_LINE_STRIP);
    for (i=-2;i<pnt.num;i+=2) // process whole curve
        { // here create the call sequence (select control points)
        j=i-2; if (j<0) j=0; if (j>=pnt.num) j=pnt.num-2; p0=pnt.dat+j;
        j=i  ; if (j<0) j=0; if (j>=pnt.num) j=pnt.num-2; p1=pnt.dat+j;
        j=i+2; if (j<0) j=0; if (j>=pnt.num) j=pnt.num-2; p2=pnt.dat+j;
        j=i+4; if (j<0) j=0; if (j>=pnt.num) j=pnt.num-2; p3=pnt.dat+j;
        for (j=0;j<2;j++) // compute curve parameters
            {
            d1=0.5*(p2[j]-p0[j]);
            d2=0.5*(p3[j]-p1[j]);
            a0[j]=p1[j];
            a1[j]=d1;
            a2[j]=(3.0*(p2[j]-p1[j]))-(2.0*d1)-d2;
            a3[j]=d1+d2+(2.0*(-p2[j]+p1[j]));
            }
        for (t=0.0;t<=1.0;t+=0.05)  // single curve patch/segment
            {
            tt=t*t;
            ttt=tt*t;
            for (j=0;j<2;j++) p[j]=a0[j]+(a1[j]*t)+(a2[j]*tt)+(a3[j]*ttt);
            glVertex2dv(p);
            }
        }
    glEnd();
    glFlush();
    SwapBuffers(hdc);
    }
//---------------------------------------------------------------------------

我认为曲线不会自相交，我尝试的所有n也没有出现自相交的情况，因为圆角只在边缘附近进行，并且递归增加时也会进行比例缩放，因此间隙保持不变。

我使用了VCL中的AnsiString类型，它是一种字符串（从索引1开始访问！）能够进行字符串运算，如添加字符串等...

我还使用了我的自定义动态列表模板，因此：
List<double> xxx;与double xxx[];相同
xxx.add(5);将5添加到列表末尾
xxx[7]访问数组元素（安全）
xxx.dat[7]访问数组元素（不安全但直接快速访问）
xxx.num是数组的实际使用大小
xxx.reset()清除数组并设置xxx.num=0
xxx.allocate(100)预分配100个项目的空间

对于曲线点，您可以使用任何可用的动态列表结构。

渲染由OpenGL 1.0（旧式API）完成，因此移植应该很容易...

功能：

void turtle_hilbert(AnsiString &s,double &a,int n);

将生成海龟图形字符串s，表示第n次希尔伯特曲线迭代。 a只是缩放因子（线段长度），使整个曲线适合于单位正方形<0,1>。

更多信息请参见相关内容：

• 如何产生多点线性插值？

- Spektre