空间填充曲线详解
线是一维的,正方形是二维的,所以一条线永远盖不住一个正方形,这似乎是显而易见的。1890 年,朱塞佩·皮亚诺证明这是可以做到的:存在一条连续曲线,它经过正方形的每一个点。这一发现迫使数学家重新思考什么是曲线、什么是维数;一个世纪之后,同样的这些曲线又在计算机里把地图和图像的数据排得井然有序。
点和正方形一样多
1877 年,格奥尔格·康托尔证明了一条线段上的点恰好和一个正方形里的点一样多:正方形的每一个点,都能与线段上专属于它的一个点配成一对。他在给理查德·戴德金的信中写道:“我看到了,但我不相信。”不过,康托尔的配对方式毫无章法地跳来跳去;它把线撕成了尘埃。悬而未决的问题是:一条线能否不被撕碎地,也就是连续地,盖住一个正方形。
皮亚诺曲线
1890 年,意大利数学家朱塞佩·皮亚诺给出了答案:可以。他只用公式、没有配一幅图,描述了一条经过单位正方形每一个点的连续曲线。他的构造把正方形切成 9 个小正方形,以 S 形弯依次走过它们,然后在每个小正方形里重复这一过程,如此一遍又一遍。
希尔伯特的图
一年后,大卫·希尔伯特发表了一个更简单的版本,并配上了那幅让这个想法变得看得见的图。把正方形切成 4 块,用一条弯折的线把各块的中心连起来。然后把每个小正方形再切成 4 块,照样再做一遍,并转动这些小副本,让线从一块接着走进下一块。第 n 层的曲线经过 4ⁿ 个格子;真正填满正方形的,是所有层级的极限。1900 年,伊莱基姆·黑斯廷斯·摩尔给出了一个终点回到起点的变体,即一个闭合的环。
极限为什么成立
盯住线上的一个点,比如位于全长三分之一处的那个点。在第 1 层,它落在 4 个格子中的一个里。每升一层,它都会移动,但始终留在那个格子里面,接着留在它的四分之一里面,依此类推:也就是留在一个边长每次减半的格子里面。所以它的位置会稳定下来,线上的每一个点也都是如此。这个极限是一条连续曲线。又因为每一层都走遍一个越来越细的网格中的每个格子,极限曲线可以任意接近正方形的每一个点,而由于它是连续的,它也就到达了这个点。
做不到一一对应
空间填充曲线必须付出代价。1879 年,欧根·内托证明了一条线不可能既连续又一一对应地映射到正方形上。所以曲线必定会多次经过某些点;希尔伯特曲线经过某些点的次数可达四次。它还处处不光滑:在任何一点上都没有切线。
长度与维数
第 n 层希尔伯特曲线的长度是正方形边长的 2ⁿ − 2⁻ⁿ 倍,大约是上一层的两倍。长度的增长没有止境,但曲线从不离开正方形。一条曲线若由 4 个缩小到一半的自身副本组成,维数就是 log 4 / log 2 = 2,正是它所填满的正方形的维数。皮亚诺曲线有 9 个缩小到三分之一的副本:log 9 / log 3 = 2,结果相同。
保持邻近关系
希尔伯特曲线有一个让它大有用处的性质:在线上靠得近的点,到了正方形里仍然靠得近。反过来却不总是成立:两个相邻的格子在线上可能相距很远。计算机利用这条曲线,把地图瓦片、像素、地球上的地点这类二维数据存成一维的顺序,同时让大多数邻居仍然彼此靠近。盖伊·莫顿于 1966 年在 IBM 提出的 Z 序,通过交错两个坐标的二进制位来完成同样的工作。它算起来更快,但保持邻近关系的效果较差,因为它会跳跃。
高斯帕的 flowsnake 与谢尔宾斯基箭头曲线
并非每一条空间填充曲线填满的都是正方形。比尔·高斯帕 1973 年提出的曲线,自 1976 年马丁·加德纳撰文介绍以来就以 flowsnake 之名为人所知,它在三角形网格上延伸,把每条线段换成七条线段。它填满的是高斯帕岛,一个有着分形海岸线的形状,七个这样的形状可以拼成一个更大的同样形状。瓦茨瓦夫·谢尔宾斯基的箭头曲线乍看之下与它相似,但每条线段只换成三段、大小缩为一半,因此什么也填不满:它描出的是谢尔宾斯基三角形,维数为 log 3 / log 2 ≈ 1.585。
动手探索
打开空间填充曲线探索器,按“播放”,观看画笔把希尔伯特曲线的每一层从头画到尾。再换成皮亚诺的 S 形弯、摩尔的闭合环、会跳跃的 Z 序、高斯帕的 flowsnake 和箭头曲线。把画笔放到曲线上的任意位置,或者放到图下方的数轴上,看看哪一步落在哪个格子里;再打开“显示上一层级”,看看每一步是怎样变成一整个弯折的。
常见问题
谁发现了第一条空间填充曲线?
朱塞佩·皮亚诺,在 1890 年。正因如此,空间填充曲线也叫皮亚诺曲线。大卫·希尔伯特 1891 年的曲线最为著名,因为希尔伯特是第一个为这种构造画出图来的人。
空间填充曲线是分形吗?
它的构造方式和分形一样,由自身的缩小副本拼成。但它的分形维数是 2,是一个整数,因为完成后的曲线覆盖一块面积。谢尔宾斯基箭头曲线的维数约为 1.585,才是通常意义上的分形。
希尔伯特曲线有多长?
第 n 层的长度是正方形边长的 2ⁿ − 2⁻ⁿ 倍:第 1 层是 1.5,第 4 层是 15.94,第 8 层接近 256。极限曲线无限长。
探索器最多能画多少层?
希尔伯特曲线、摩尔曲线和 Z 序最多 8 层,也就是 256 × 256 个格子的网格;皮亚诺曲线(243 × 243 个格子)和高斯帕曲线(16,807 条线段)最多 5 层;谢尔宾斯基箭头曲线最多 10 层(59,049 条线段)。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
打开空间填充曲线探索器