论文部分内容阅读
Hilbert曲线是一条能填满正方形的经典的分形曲线之一,由大卫·希尔伯特在1891年提出。Hilbert曲线具有三个特点:(1)它可以不间断地遍历一个正方形中的所有点,当阶n趋向无穷大时,它充满一个正方形,曲线的长度也将无穷大;(2)分布在一个正方形中的Hilbert曲线十分曲折但不会交叉,连续但不可导;(3)它具有自相似性。自相似性是所有分形曲线的主要特征之一。
由于Hilbert曲线能尽可能地保持原空间中相邻点的相关性,因此Hilbert曲线已在图像处理,电路设计方面有一定的用途。另外,由于Hilbert曲线的图案相当精美,因此它也常被用在艺术创作上。
一、Hilbert曲线的生成方法
目前生成Hilbert曲线的方法主要有L系统方法,下面做简要的介绍:
L系统法是符号串重写系统。如果将符号解释成以某种方式绘制曲线或图形,则只要生成符号串,就等于生成了曲线或图形。L系统从公理(初始符号串)开始,将变换规则多次作用于符号串之上,最后生成了一个较长的符号串;利用该符号串的集合含义来绘制曲线或图形。
符号表V={L,R,F,+,-}功w=L
规则集合P={L→+RF-LFL-FR+,R→LF+RFR+FL-},(→表示在将规则作用于符号时,用→右边的符号串代替左边的符号。)
V中的各个符号都是绘制希尔伯特曲线要用到的曲线单元,假设当前方向为
水平向右,则V中各符号的几何解释如下:
L:画一个开口向上的口杯状折线,口杯的高度和底径相等,折线上的小圆
点和箭头分别表示画线的起点和方向;如图2-2(1)。
R:画一个开口向下的口杯状折线,口杯的高度和底径相等,折线上的小圆
点和箭头分别表示画线的起点和方向;如图2-2(2)。
F:向前一步,画一条直线段;如图2-2(3)
+:表示当前位置顺时针旋转90°;
-:表示当前位置逆时针旋转90°。
(1)L的几何意义 (2)R的几何意义 (3)F的几何意义
图2:生成Hilbert曲线的基本元素
从公理L出发,逐级运用规则集合P中的规则,对符号表V进行重写,可得到表示Hilbert曲线的各级符号串。生成Hilbert曲线就是一个不断将规则作用于符号的过程。需要特别注意的是,随着希尔伯特曲线级数的增加,所用到的曲线单元的尺寸是递减的。
二、基于MATLAB的Hilbert曲线的计算机仿真
用MATLAB对Hilbert曲线进行仿真的方法比较多,大多数方法的算法比较复杂,程序也比较冗长。本文在这里介绍一段由Federico Forte编写的程序,这段程序被MATLAB CENTRAL收录。
(1)由Federico Forte编写的基于MATLAB的Hilbert曲线的计算机仿真程序:
function [x,y] = hilbert(n)
%HILBERT Hilbert curve.
% [x,y]=hilbert(n) gives the vector coordinates of points
% in n-th order Hilbert curve of area 1.
% Example: plot of 5-th order curve
% [x,y]=hilbert(5);line(x,y)
if n<=0
x=0;
y=0;
else
[xo,yo]=hilbert(n-1);
x=.5*[-.5+yo -.5+xo .5+xo.5-yo];
y=.5*[-.5+xo.5+yo .5+yo -.5-xo];
(2)利用这段程序在MATALB上绘制1到9阶的Hilbert曲线的仿真结果:
由于Hilbert曲线能尽可能地保持原空间中相邻点的相关性,因此Hilbert曲线已在图像处理,电路设计方面有一定的用途。另外,由于Hilbert曲线的图案相当精美,因此它也常被用在艺术创作上。
一、Hilbert曲线的生成方法
目前生成Hilbert曲线的方法主要有L系统方法,下面做简要的介绍:
L系统法是符号串重写系统。如果将符号解释成以某种方式绘制曲线或图形,则只要生成符号串,就等于生成了曲线或图形。L系统从公理(初始符号串)开始,将变换规则多次作用于符号串之上,最后生成了一个较长的符号串;利用该符号串的集合含义来绘制曲线或图形。
符号表V={L,R,F,+,-}功w=L
规则集合P={L→+RF-LFL-FR+,R→LF+RFR+FL-},(→表示在将规则作用于符号时,用→右边的符号串代替左边的符号。)
V中的各个符号都是绘制希尔伯特曲线要用到的曲线单元,假设当前方向为
水平向右,则V中各符号的几何解释如下:
L:画一个开口向上的口杯状折线,口杯的高度和底径相等,折线上的小圆
点和箭头分别表示画线的起点和方向;如图2-2(1)。
R:画一个开口向下的口杯状折线,口杯的高度和底径相等,折线上的小圆
点和箭头分别表示画线的起点和方向;如图2-2(2)。
F:向前一步,画一条直线段;如图2-2(3)
+:表示当前位置顺时针旋转90°;
-:表示当前位置逆时针旋转90°。
(1)L的几何意义 (2)R的几何意义 (3)F的几何意义
图2:生成Hilbert曲线的基本元素
从公理L出发,逐级运用规则集合P中的规则,对符号表V进行重写,可得到表示Hilbert曲线的各级符号串。生成Hilbert曲线就是一个不断将规则作用于符号的过程。需要特别注意的是,随着希尔伯特曲线级数的增加,所用到的曲线单元的尺寸是递减的。
二、基于MATLAB的Hilbert曲线的计算机仿真
用MATLAB对Hilbert曲线进行仿真的方法比较多,大多数方法的算法比较复杂,程序也比较冗长。本文在这里介绍一段由Federico Forte编写的程序,这段程序被MATLAB CENTRAL收录。
(1)由Federico Forte编写的基于MATLAB的Hilbert曲线的计算机仿真程序:
function [x,y] = hilbert(n)
%HILBERT Hilbert curve.
% [x,y]=hilbert(n) gives the vector coordinates of points
% in n-th order Hilbert curve of area 1.
% Example: plot of 5-th order curve
% [x,y]=hilbert(5);line(x,y)
if n<=0
x=0;
y=0;
else
[xo,yo]=hilbert(n-1);
x=.5*[-.5+yo -.5+xo .5+xo.5-yo];
y=.5*[-.5+xo.5+yo .5+yo -.5-xo];
(2)利用这段程序在MATALB上绘制1到9阶的Hilbert曲线的仿真结果: