于延华, 刘玲, 杨云
东北大学 理学院, 辽宁 沈阳 110819
收稿日期：2018-05-07
基金项目：国家自然科学基金资助项目(11371080);中央高校基本科研业务费专项资金资助项目(N170504014)。
作者简介：于延华(1978-)，女，湖北荆门人，东北大学副教授。

摘要：现有刻画三维Hilbert曲线的算法大多是从始点到终点递归地计算节点坐标, 针对此类算法迭代次数较多的问题, 提出一种刻画三维Hilbert曲线的新算法.借助于构造活动标架, 得到刚体运动下的不变量，即离散曲率挠率.考虑到活动标架, 曲线节点将被重新编码.并建立曲线弯曲点位置编号与其对应的曲率挠率数对的映射, 编写相应算法使其对任意编号n, 能够输出该编号对应弯曲点的曲率挠率数对且画出弯曲点图象结构.相比于基于Matlab生成Hilbert曲线的算法Hilbert3(n), 该算法不局限于曲线的阶数、不依赖相邻阶曲线节点坐标之间的迭代.实验结果表明此算法更加高效.
关键词：活动标架Hilbert曲线离散曲率离散挠率迭代
Study of Hilbert Curve Based on Moving Frame
YU Yan-hua, LIU Ling, YANG Yun
School of Sciences, Northeastern University, Shenyang 110819, China
Corresponding author: YANG Yun, E-mail: freeuse_st @126.com
Abstract: Most algorithms for describing three-dimensional Hilbert curves calculate node coordinates from the start point to the end point recursively. Directing at the multiple iteration, a new algorithm was brought forth. By means of constructing moving frame, the invariants under rigid body motion are obtained, that is, discrete curvature and torsion. Considering moving frame, the nodes are recoded. Establishing a map between the inflection point location number and the discrete curvature and torsion of the inflection point, based on that, writing the corresponding algorithm to make it for any number n, the pairs of curvature torsion and the image structure corresponding to the inflection points can be output. Compared to the algorithm Hilbert3(n), the proposed algorithm is not limited to the order of the curve and does not depend on the iteration between the coordinates. Experimental results show that the algorithm is more efficient.
Key words: moving frameHilbert curvediscrete curvaturediscrete torsioniteration
Hilbert曲线源于经典的Peano曲线族, 是所有能够填充满二维或更高维区域的离散分形^[1]曲线总称.Hilbert曲线在图象存储和检索、空间数据库索引^[2]等领域得到了广泛的应用.因此空间Hilbert曲线的画法已经得到越来越多的关注.
已有刻画三维Hilbert曲线的算法一般是通过不断8等分一个正方体区域, 从始点到终点递归地计算画线的位置的过程, 因此方向是这些运算要考虑的问题.由于这些算法大都是对曲线的每条线段逐渐细分做递归运算, 当迭代次数较大时计算非常耗时, 因此有必要提出一个有效减少迭代次数的算法.
考虑到活动标架^[3-6], 将重新编码三维Hilbert曲线的节点, 建立曲线弯曲点位置号码与基于活动标架得到的弯曲点曲率挠率数对的映射^[7], 不必考虑曲线方向.通过编写相应的程序, 对任意一个实数n, 能够输出对应弯曲点的曲率挠率数对并且画出相应弯曲点图象结构.
1 Hilbert曲线的性质Hilbert曲线是离散曲线的一种, 有二维三维甚至更高维的情形, 本文只考虑三维.三维Hilbert曲线能够不自交地充满正方体.经典描述如下:首先将正方体8等分, 求出各个小正方体的中心, 并将它们按照某种顺序依次连接, 得到图 1a所示折线; 其次将各个小正方体再细分为8个相同的小正方体, 并连接各个小正方体的中心, 得到图 1b; 按照这种方法不断细分下去, 并按一定规则一一连接, 就可得到图 1的Hilbert曲线.
图 1(Fig. 1)

图 1 Hilbert曲线Fig.1 Hilbert curve (a)—1阶Hilbert曲线；(b)—2阶Hilbert曲线；(c)—n阶Hilbert曲线.

第n阶Hilbert曲线与第n+1阶Hilbert曲线是仿射相等的^[8].考虑以Hilbert曲线边缘切向量^[9]t_k-2，t_k-1以及t_k-2×t_k-1为活动标架.通常地, 第n阶曲线有8ⁿ个节点, 本文中仅使用曲线的弯曲点, 即出现3个点或3个以上点共线的情况, 仅标记直线的第一个点和最后一个节点使用, 如图 2所示第24, 25, 26点, 将去掉第25点, 将第26点标记为25, 按照如上所述的标记方法.
图 2(Fig. 2)

图 2 共线点Fig.2 Collinear point

定理1??第n阶与第n+1阶Hilbert曲线弯曲点总数N(n)及N(n+1)满足:

(1)

N(1)=8, 经过简单的计算, 可得第n阶Hilbert曲线弯曲点总数为

(2)

2 基于活动标架计算离散曲率挠率及其迭代特点经过重新编码, 对于三维Hilbert曲线, 由于切向量满足t_k-2⊥t_k-1?k∈Z⁺, 且k≥3.以t_k-2, t_k-1及t_k-2×t_k-1为活动标架, 有
经过简单的推导, 有

(3)

第3k-1阶Hilbert曲线7组连接点中的第1, 2, 7组连接点^[10]如图 3所示.其中图 3a，3b，3c的位置向量分别为
图 3(Fig. 3)

图 3 从第3k-2阶迭代到3k-1阶的部分连接点Fig.3 Part of joints of iterative process from the 3k-2nd to the 3k-1st step (a)—第1组连接点；(b)—第2组连接点；(c)—第7组连接点.

同理从第3k-1阶迭代到第3k阶及从第3k阶迭代到3k+1阶分别产生7组类似的连接点.
定理2??空间Hilbert曲线在每个弯曲点的离散曲率和挠率满足
记
可以用下面的方式展示Hilbert曲线曲率挠率序列的迭代结果：
n=1时, (-1, 0)A(-1, 0);
n=2时, (-1, 0)AB₂AC₂AD₂AC₂AE₂AC₂AF₂A(-1, 0)，如果用K₂表示第一个(-1, 0)和最后一个(-1, 0)的中间曲率挠率数对序列, 即
从而
很容易得到如下的图式规律：
曲率挠率数对构成的字母序列的长度满足

(4)

3 弯曲点曲率挠率位置特点首先计算3k-1阶曲线弯曲点的离散曲率和挠率, 显然由3k-2阶曲线可以得到以第3个点为起点以第个点为终点的部分Hilbert曲线的每个弯曲点的曲率和挠率数对
如图 3所示, 已经得到第3k-1阶的Hilbert曲线连接点的曲率挠率数对, 且3k-1阶曲线连接点以外的其他弯曲点满足如下等式:
其中，.
因此容易通过3k-2阶曲线的弯曲点的曲率挠率得到3k-1阶曲线全部弯曲点的曲率挠率.
类似地用上述方法, 可以分别得到第3k阶和第3k+1阶的曲率挠率数对.
4 算法分析Hilbert3(n)是计算n阶Hilbert曲线上所有点三维坐标的经典算法, 在此基础上编写计算曲线任意弯曲点曲率挠率的算法, 并将此算法与本文算法进行比较, 见表 1.
表 1(Table 1)

表 1 算法计算时间比较Table 1 Comparison of calculation time of different algorithm s 算法 n 100 1 000 10 000 100 000 本文算法 2.15 2.13 3.94 4.00 Hilbert3(n) 0.81 1.25 11.41 519.56

表 1 算法计算时间比较 Table 1 Comparison of calculation time of different algorithm

算法速度提高的主要原因是基于三维Hilbert曲线弯曲点离散曲率挠率分布特点有效减少了迭代次数.以k=1, l=3为例, 由
可知, (κ(57), τ(57))的值可以通过直接(κ(3), τ(3))获得, 而不必通过计算前面57个弯曲点的三维坐标来获得(κ(57), τ(57)), 随着k的增大, 减少的迭代次数是呈指数增长的, 因此有效提高了刻画Hilbert曲线任意弯曲点曲率挠率的效率.
5 结语针对刻画三维Hilbert曲线这个传统问题进行研究, 给出了一套对于任意实数n, 快速输出Hilbert曲线第n个弯曲点的曲率挠率数对, 并画出其相应的图象结构的算法.基于对三维Hilbert的深入分析, 在自相似特征中基于活动标架归纳出Hilbert曲线弯曲点的曲率挠率数对分布特点, 最后提出了基于该思想的输出Hilbert曲线任意弯曲点曲率挠率及该点处图象结构的算法.
参考文献

[1]	Olver P J.Modern developments in the theory applications of moving frames[EB/OL]. (2015-03-06).https://www.lms.ac.uk/sites/lms.ac.uk/files/olver_l1_final_151212.pdf.
[2]	Yang Y, Yu Y H.The moving frame on the fractal curves[EB/OL]. (2016-12-16)[2018-05-03]. https://arxiv.org/abs/1612.05341v1.
[3]	Yang Y, Yu Y H.Moving frame and integrable system of the discrete centroaffine curves in R3[EB /OL]. (2016-11-27)[2018-05-03]. https://arxiv.rg/abs/1601.06530v2.
[4]	Mansfield E, MariBeffa G, Wang J P. Discrete moving frames and discrete integrable systems[J].Foundations of Computational Mathematics, 2013, 13: 545–582.DOI:10.1007/s10208-013-9153-0
[5]	Hu N. Centroaffine space curves with constant curvatures and homogeneous surfaces[J].Journal of Geometry, 2011, 102: 103–114.DOI:10.1007/s00022-012-0105-7
[6]	文志英. 分形几何理论与应用[M]. 杭州: 浙江科学技术出版社, 1998: 1-31. ( Wen Zhi-ying. Theory and application of fractal geometry[M]. Hangzhou: Zhejiang Science and Technology Press, 1998: 1-31.)
[7]	Christian B, Stefan B, Daniel A K. Searching in high dimensional space index structures for improving the performance of multimedia databases[J].ACM Computing Surveys(CSUR), 2001, 33(3): 322–373.DOI:10.1145/502807.502809
[8]	梅向明, 刘增贤, 王汇淳, 等. 高等几何[M]. 北京: 高等教育出版社, 2008: 1-85. ( Mei Xiang-ming, Liu Zeng-xian, Wang Hui-chuan, et al. Advanced geometry[M]. Beijing: Higher Education Press, 2008: 1-85.)
[9]	Yang Y.The frenet-serret formula of a discrete centroaffine curve[EB/OL]. (2016-11-27)[2018-05-15]. https://arxiv.org/abs/1601.06530v1.
[10]	Olver P J. Joint invariant signatures[J].Foundations of Computational Mathematics, 2001, 1(1): 3–68.DOI:10.1007/s10208001001