Scratch画分形几何图系列25：L系统画希尔伯特填充曲线

我们用L系统化了一些分形曲线，在前面的文章里也曾见过“填充曲线”的影子。本文开始来认识几个典型的填充曲线。首先见识希尔伯特曲线。

（1）Hilbert曲线是一种能填充满一个平面正方形的分形曲线（空间填充曲线），由大卫·希尔伯特在1891年提出，如图所示。Hilbert曲线通过把一个正方形空间不断的分成4个子空间，再把小正方形的中心点连接起来得到的曲线，即希尔伯特曲线。在希尔伯特曲线的编码映射中，使用U字型来访问每个空间，对分成的4个子空间也同样使用U字形访问，但要调整U字形的朝向，才能使得相邻的空间能够衔接起来。

分级示意

（2）如下图，在第一层级时，选择一个起始点和方向，然后用0到3依次给四个子空间编号。然而，当层数大于1时，维护总体的邻接特性，是一件较为复杂的过程。

找方格中心点示意

通过不断地观察，我们发现，子空间的曲线是由原空间的简单变换得来，而且只存在四种变换方式，并且相同的变换也适用于子空间的子空间等等。给定一个空间，我们根据它的U字形曲线朝向来确定其四个子空间的U字形曲线朝向和编号。如下图中 (a)所示，当U字形朝向为下时，Hibert曲线从左下角开始按照顺时针方向分别对其四个子空间编号为0到3，并且进一步划分四个子空间时，它们的U字型朝向分别为左、下、下、右。其它朝向的U字形变换和编号方式，如下图中 (b)(c)(d)所示。同样地，Hilbert曲线会按照曲线的前进顺序从整数0开始给所有最小的网格编码。

四种变换方式

（3）由此可见，它的生成机制与箭头谢尔宾斯基三角有点类似，是由两套分规则相互调用生成。A是从左下角开始按顺时针方向画一个U形的三边，B是从右下角开始按逆时针方向画一个U形的三边。只不过连接相邻两个U形的那条线段是不递归的。

L系统示意图

（4）我们根据上面的生成规则定义L系统如下：

公理： A

规则： A→ +BF−AFA−FB+ ； B→ −AF+BFB+ FA− 。

符号： F：前进 ；+：左转90 ；−：右转90；A，B：什么都不做。

（4）根据L系统定义写程序，根据级数确定划分的小方格的个数和大小，以确定F前进的长度。

规则A递归程序

规则B递归程序

主程序

5级填充曲线

7级希尔伯特填充曲线

8级填充曲线

（5）再增加级数N的值，就只能见到红色一片了。

9级就看不见线了