math - 平滑希尔伯特曲线

Question

我正在尝试平滑 Hilbert curve 所采用的路径.我可以定义点并用直线连接它们，但我想要一条不会使边缘如此尖锐的路径。我尝试使用越来越高阶的贝塞尔曲线连接曲线，但这不起作用，当我尝试重新连接它们时，路径中总是存在“扭结”:

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

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我试过它们没有，因为舍入被限制在非常靠近边缘的地方，递归的增加也会缩放它，所以差距仍然存在。

我用了AnsiString来自 VCL 的类型是字符串(从索引 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 -th 希尔伯特曲线迭代。 a只是缩放(线长)所以整条曲线适合单位正方形 <0,1> .

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

• How can i produce multi point linear interpolation?