Hilbert曲线源于经典的Peano曲线族, 是所有能够填充满二维或更高维区域的离散分形[1]曲线总称.Hilbert曲线在图象存储和检索、空间数据库索引[2]等领域得到了广泛的应用.因此空间Hilbert曲线的画法已经得到越来越多的关注.
已有刻画三维Hilbert曲线的算法一般是通过不断8等分一个正方体区域, 从始点到终点递归地计算画线的位置的过程, 因此方向是这些运算要考虑的问题.由于这些算法大都是对曲线的每条线段逐渐细分做递归运算, 当迭代次数较大时计算非常耗时, 因此有必要提出一个有效减少迭代次数的算法.
考虑到活动标架[3-6], 将重新编码三维Hilbert曲线的节点, 建立曲线弯曲点位置号码与基于活动标架得到的弯曲点曲率挠率数对的映射[7], 不必考虑曲线方向.通过编写相应的程序, 对任意一个实数n, 能够输出对应弯曲点的曲率挠率数对并且画出相应弯曲点图象结构.
1 Hilbert曲线的性质Hilbert曲线是离散曲线的一种, 有二维三维甚至更高维的情形, 本文只考虑三维.三维Hilbert曲线能够不自交地充满正方体.经典描述如下:首先将正方体8等分, 求出各个小正方体的中心, 并将它们按照某种顺序依次连接, 得到图 1a所示折线; 其次将各个小正方体再细分为8个相同的小正方体, 并连接各个小正方体的中心, 得到图 1b; 按照这种方法不断细分下去, 并按一定规则一一连接, 就可得到图 1的Hilbert曲线.
第n阶Hilbert曲线与第n+1阶Hilbert曲线是仿射相等的[8].考虑以Hilbert曲线边缘切向量[9]tk-2,tk-1以及tk-2×tk-1为活动标架.通常地, 第n阶曲线有8n个节点, 本文中仅使用曲线的弯曲点, 即出现3个点或3个以上点共线的情况, 仅标记直线的第一个点和最后一个节点使用, 如图 2所示第24, 25, 26点, 将去掉第25点, 将第26点标记为25, 按照如上所述的标记方法.
定理1 第n阶与第n+1阶Hilbert曲线弯曲点总数N(n)及N(n+1)满足:
(1) |
N(1)=8, 经过简单的计算, 可得第n阶Hilbert曲线弯曲点总数为
(2) |
经过重新编码, 对于三维Hilbert曲线, 由于切向量满足tk-2⊥tk-1∀k∈Z+, 且k≥3.以tk-2, tk-1及tk-2×tk-1为活动标架, 有
经过简单的推导, 有
(3) |
第3k-1阶Hilbert曲线7组连接点中的第1, 2, 7组连接点[10]如图 3所示.其中图 3a,3b,3c的位置向量分别为
同理从第3k-1阶迭代到第3k阶及从第3k阶迭代到3k+1阶分别产生7组类似的连接点.
定理2 空间Hilbert曲线在每个弯曲点的离散曲率和挠率满足
记
可以用下面的方式展示Hilbert曲线曲率挠率序列的迭代结果:
n=1时, (-1, 0)A(-1, 0);
n=2时, (-1, 0)AB2AC2AD2AC2AE2AC2AF2A(-1, 0),如果用K2表示第一个(-1, 0)和最后一个(-1, 0)的中间曲率挠率数对序列, 即
从而
很容易得到如下的图式规律:
曲率挠率数对构成的字母序列的长度满足
(4) |
首先计算3k-1阶曲线弯曲点的离散曲率和挠率, 显然由3k-2阶曲线可以得到以第3个点为起点以第
如图 3所示, 已经得到第3k-1阶的Hilbert曲线连接点的曲率挠率数对, 且3k-1阶曲线连接点以外的其他弯曲点满足如下等式:
其中,
因此容易通过3k-2阶曲线的弯曲点的曲率挠率得到3k-1阶曲线全部弯曲点的曲率挠率.
类似地用上述方法, 可以分别得到第3k阶和第3k+1阶的曲率挠率数对.
4 算法分析Hilbert3(n)是计算n阶Hilbert曲线上所有点三维坐标的经典算法, 在此基础上编写计算曲线任意弯曲点曲率挠率的算法, 并将此算法与本文算法进行比较, 见表 1.
算法速度提高的主要原因是基于三维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 |