平滑希尔伯特曲线

Question

我正在努力理清 Hilbert curve 所走过的路。我可以定义点并用直线连接它们，但我想要一条不会使边缘如此尖锐的路径。我尝试使用越来越高阶的贝塞尔曲线连接曲线，但这不起作用，当我尝试重新连接它们时，路径中总是有 'kinks'：

我觉得这是一个已解决的问题，但我不是在寻找合适的术语。

Answer 1

为此使用分段三次如何...如果 BEZIER SPLINE 或其他什么并不重要。您只需要将补丁与正确的点调用序列连接起来，而您显然没有这样做。这是我使用 my Interpolation cubics 和正确调用顺序的示例：

Gray是海龟图形原始Hilbert曲线，Aqua是相同点的插值三次曲线...

很好奇，所以我想实现它，但我花了一段时间才弄清楚并实现 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 项预分配 space

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

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

函数：

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

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

有关更多信息，请参阅相关内容：

平滑希尔伯特曲线

Smooth Hilbert curves

math

graphics

bezier

curve-fitting