平滑希尔伯特曲线 [英] Smooth Hilbert curves
问题描述
我正在尝试平滑
我觉得这是一个已解决的问题,但我没有在寻找正确的术语.
如何为此使用分段三次...不管是 BEZIER SPLINE 还是其他什么.您只需要将补丁与正确的点调用序列连接起来,而您显然没有这样做.这是我使用
Gray 是海龟图形的原始 Hilbert 曲线,Aqua 是相同点的内插三次曲线...
很好奇所以我想实现这个,但我花了一段时间来弄清楚和实现 2D Hilbert 曲线(我使用海龟图形),因为我以前从未使用过它们.这里OpenGL VCL C++源代码:
//---------------------------------------------------------------------双 ha=0.0;AnsiString hs="";//海龟图形列表<double>点;//二维点列表//---------------------------------------------------------------------------voidturtle_mirror(AnsiString &s)//交换 l,r{国际我,我;字符 c;for (l=s.Length(),i=1;i<=l;i++){c=s[i];if (c=='l') s[i]='r';如果 (c=='r') s[i]='l';}}//---------------------------------------------------------------------------voidturtle_hilbert(AnsiString &s,double &a,int n)//计算 hilbert 曲线turtle string s,n 次迭代的线段大小a{国际我,我;字符 c;AnsiString s0;if (s=="") { l=1;s="frfrf";}//假设起始左下角向上,初始化希尔伯特曲线对于 (i=0;i &xy,double x,double y,double dx,double dy,const AnsiString &s){国际我,我;字符 c;双 q;l=s.Length();xy.num=0;//清晰的列表xy.add(x);//添加点xy.add(y);对于 (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();}//---------------------------------------------------------------------------无效 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);//希尔伯曲线覆盖<-1,+1>范围如果 (hs==""){海龟希尔伯特(hs,ha,3);//初始化海龟字符串龟计算(pnt,-0.9,-0.9,0.0,1.8*ha,hs);//曲线拟合的初始点列表}//将 hs,ha 渲染为海龟图形glColor3f(0.4,0.4,0.4);海龟绘图(-0.9,-0.9,0.0,1.8*公顷,小时);//将 pnt[] 渲染为插值三次int i,j;双 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) j=pnt.num-2;p0=pnt.dat+j;j=i;如果 (j<0) j=0;如果 (j>=pnt.num) j=pnt.num-2;p1=pnt.dat+j;j=i+2;如果 (j<0) j=0;如果 (j>=pnt.num) j=pnt.num-2;p2=pnt.dat+j;j=i+4;如果 (j<0) j=0;如果 (j>=pnt.num) j=pnt.num-2;p3=pnt.dat+j;for (j=0;j<2;j++)//计算曲线参数{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)//单曲线补丁/段{tt=t*t;ttt=tt*t;对于 (j=0;j<2;j++) p[j]=a0[j]+(a1[j]*t)+(a2[j]*tt)+(a3[j]*ttt);glVertex2dv(p);}}glEnd();glFlush();交换缓冲区(hdc);}//---------------------------------------------------------------------------
我不认为曲线会自相交,对于所有 n
我试过他们没有因为舍入被限制在非常靠近边缘的地方并且增加递归也会缩放它所以间隙遗体.
我使用了 VCL 中的 AnsiString
类型,它是字符串(从索引 1
访问!)能够进行字符串运算,例如添加字符串等..
我也使用我的动态列表模板,所以:List
等同于 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);
将生成代表第n
次希尔伯特曲线迭代的海龟图形字符串s
.a
只是缩放(线长),因此整个曲线适合单位平方 <0,1>
.
有关更多信息,请参阅相关内容:
I'm trying to smooth out the path taken by a Hilbert curve. I can define the points and connect them by straight lines, but I want a path that doesn't take the edges so sharply. I attempted to connect the curve using Bezier curves of higher and higher orders but this doesn't work, there are always 'kinks' in the path as I try to reconnect them:
I feel like this a solved problem, but I'm not searching for the right terms.
How about using piecewise cubics for this... Does not really matter if BEZIER SPLINE or whatever. You just need to connect the patches with proper point call sequence which you clearly did not do. Here is my example using my Interpolation cubics with proper call sequence:
Gray is the turtle graphics original Hilbert curve and Aqua is the interpolated cubic curve for the same points ...
Was curious so I wanted to implement this but Took me a while to figure out and implement 2D Hilbert curves (I used turtle graphics) as I never used them before. Here OpenGL VCL C++ source code for this:
//---------------------------------------------------------------------------
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);
}
//---------------------------------------------------------------------------
I do not think the curves would self-intersect and for all the n
I tried they did not because the rounding is confined very near to the edges and increasing recursion will scale it too so the gap remains.
I used AnsiString
type from VCL which is string (accessed from index 1
!) capable of string arithmetics like adding string etc ...
I also use mine dynamic list template so:
List<double> xxx;
is the same as double xxx[];
xxx.add(5);
adds 5
to end of the list
xxx[7]
access array element (safe)
xxx.dat[7]
access array element (unsafe but fast direct access)
xxx.num
is the actual used size of the array
xxx.reset()
clears the array and set xxx.num=0
xxx.allocate(100)
preallocate space for 100
items
for the curve points you can use any dynamic list structure you got at your disposal instead.
The rendering is done by OpenGL 1.0 (old style api) so porting that should be easy ...
Function:
void turtle_hilbert(AnsiString &s,double &a,int n);
will generate turtle graphics string s
representing the n
-th Hilbert curve iteration. The a
is just scaling (line length) so the entire curve fit into unit square <0,1>
.
For more info see related:
这篇关于平滑希尔伯特曲线的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!