生成P3平铺

# 生成 P3 铺砌 来源：https://k-monk.org/blog/generating-the-p3-tiling/ - 首页 (https://k-monk.org/) - 博客 (https://k-monk.org/blog) - RSS (https://k-monk.org/feed.xml) ### 2026\-06\-28 你听说过彭罗斯铺砌吗？今天，我想描述一种可以用来生成它们的算法。我希望这篇文章能为一些未来主题提供必要的背景材料，这些主题的细节我暂且保密。 ## 铺砌简介 (https://k-monk.org/blog/generating-the-p3-tiling/#introduction-to-tilings) 首先，什么是铺砌？数学家将任何无间隙覆盖二维平面的图案称为二维平面的*铺砌*。例如，想象一个无限延伸的棋盘。 image 铺砌中出现的一组形状称为它的*原瓷砖*。棋盘铺砌只使用一种原瓷砖，即正方形。 如果一个铺砌可以通过某种方式平移整个平面回到起点，则称为*周期性的*。棋盘铺砌是周期性的，因为例如，你可以将整个铺砌向右平移一个方格，得到相同的图案。如果铺砌没有这样的平移对称性，则称为*非周期性的*。 彭罗斯铺砌是已知的第一种仅使用两种原瓷砖的非周期平面铺砌。它们由罗杰·彭罗斯于20世纪70年代发现。据我所知，有三种变体，称为P1、P2和P3。P1使用四种原瓷砖，而P2和P3仅使用两种。今天我们重点讨论P3。 ### P1 image ### P2（风筝与飞镖） image ### P3（菱形） image ## 细分规则 (https://k-monk.org/blog/generating-the-p3-tiling/#subdivision-rules) 以下四条规则构成了生成P3的算法： image 我们有四个三角形，通过其颜色标识。每条规则解释了如何将一个三角形替换为一组更小的三角形。从四个三角形中的任何一个开始，我们可以递归地应用这些规则。每轮细分都会产生起始三角形更详细的铺砌。使用下面的按钮，观察执行规则几次会发生什么。 这些原瓷砖被称为罗宾逊三角形，以发现者拉斐尔·罗宾逊命名，他在彭罗斯发现P2和P3之后不久发现了它们。如果你对历史感兴趣，请参见Grünbaum和Shephard的《*Tilings and Patterns*》(https://archive.org/details/isbn_0716711931) 第10.3节。 你可能注意到罗宾逊三角形看起来不像P3中的菱形。其实，这些规则总是会成对生成图案。锐角三角形成对出现，钝角三角形也成对出现；总是在底边连接（除了边缘的瓷砖）。因此，一旦我们完成细分，我们可以将这些对缝合在一起得到菱形。上面P3渲染图中的红色菱形是锐角对，蓝色菱形是钝角对。 为什么这些规则保证以这种方式成对生成？本质上，是通过对细分规则的结构归纳。 ## 项重写系统 (https://k-monk.org/blog/generating-the-p3-tiling/#a-term-rewriting-system) 我声称细分规则构成一种算法。这只在某种程度上成立。规则以图形方式给出，计算机不能直接操作图片。 有一种框架可以写出适合机器执行的此类系统：项重写。让我们看看是否可以将这些规则表达为项重写规则。如果你之前没有接触过项重写，不用担心，我会边讲边解释。Baader和Nipkow的《*Term Rewriting and All That*》第一章是理论的好介绍，如果你想了解的话。 一个罗宾逊三角形由其颜色及其顶点唯一标识。假设我们选择字母C、D、X和Y来表示上面呈现顺序的四种三角形颜色。那么，例如，一个具有顶点p、q和r的浅蓝色三角形可以符号表示为C(p, q, r)。那是一个*项*——一段语法——我们想要将细分规则表达为对项的操作。 image 上面是细分规则的复制，添加了标签供参考。注意，每条细分规则至少创建一个新顶点。细分创建的顶点在每条规则的右侧标记为S和T。 如果我们打算将规则表达为对项的操作，我们需要一种用父顶点来表达S和T的方法。罗宾逊三角形有一个很好的几何性质可以利用：S和T总是位于沿边的1/φ距离处，其中φ是黄金比例。黄金比例出现在这里，是因为它是正五边形对角线与其边长的比值，而彭罗斯铺砌都是关于五重旋转对称的。我们将写p ⇒ q来表示从p到q的1/φ距离处到达的点。 有了这些，我们准备好将细分规则表达为项重写规则。 C(p, q, r) → C(q, r ⇒ q, p) × Y(r, p, r ⇒ q) D(p, q, r) → D(r ⇒ p, p, q) × X(q, r, r ⇒ p) X(p, q, r) → C(r, p ⇒ r, p ⇒ q) × X(q, r, p ⇒ q) × Y(p, p ⇒ q, p ⇒ r) Y(p, q, r) → D(q ⇒ r, r, q ⇒ p) × X(q ⇒ p, q, q ⇒ r) × Y(r, p, q ⇒ p) 颜色符号C、D、X和Y在项重写文献中被称为“函数符号”：具有固定元数（固定数量的输入）的名称。分割符号⇒和乘积符号×也是函数符号，但为了清晰起见，我选择以中缀形式使用它们。如果完全正式，我们需要为二元和三元分别使用不同的乘积符号。 小写字母p、q和r是变量。它们取值范围为任意项。每条规则的左侧是一个模式；只要找到其中变量的满足实例，就可以应用该规则。 转换为代码，可能类似于我为生成此页面上的P3图像而编写的递归函数： `` function generateP3(type, p, q, r, depth) { const triangle = { type: type, depth: depth, p: p, q: q, r: r, }; if (depth > 0) { switch (type) { case "C": { const s = midpoint(r, q); triangle.y = generateP3("Y", r, p, s, depth - 1); triangle.c = generateP3("C", q, s, p, depth - 1); break; } case "D": { const s = midpoint(r, p); triangle.x = generateP3("X", q, r, s, depth - 1); triangle.d = generateP3("D", s, p, q, depth - 1); break; } case "X": { const d = midpoint(p, q); const e = midpoint(p, r); triangle.x = generateP3("X", q, r, d, depth - 1); triangle.y = generateP3("Y", p, d, e, depth - 1); triangle.c = generateP3("C", r, e, d, depth - 1); break; } case "Y": { const d = midpoint(q, p); const e = midpoint(q, r); triangle.x = generateP3("X", d, q, e, depth - 1); triangle.y = generateP3("Y", r, p, d, depth - 1); triangle.d = generateP3("D", e, r, d, depth - 1); break; } default: { console.log("Unexpected color."); break; } } } return triangle; } `` ## 坐标系 (https://k-monk.org/blog/generating-the-p3-tiling/#a-coordinate-system) 利用一些巧妙的数学，我们可以仅使用整数坐标表示P3铺砌中的所有顶点。如果我们需要比较点的相等性，这将非常有用；这意味着我们不必担心浮点数不精确。 基本思想是集合 {ζ³, ζ², ζ, 1} 其中 ζ = e^(πi/5) 构成了P3坐标空间的一组基。我们可以将P3铺砌中的任何点表示为这四个向量的线性组合（整数系数）。 为了证明这一点，我们将通过对细分规则的结构归纳来论证。首先，注意 φ 和 φ⁻¹ 在该系统中都有表示： φ = 1 + ζ² - ζ³ 1/φ = ζ² - ζ³ 起始坐标（即外部 **X** 三角形的点）是可表示的： P = 0 Q = 1 R = ζ/φ 细分规则中使用的中点运算是通过1/φ的线性插值： p ⇒ q = p + (q - p)/φ = p + φ⁻¹ (q - p) 因此，我们只需要证明这个跨度在加法、减法和乘法下是封闭的；这些是计算中点所需的运算。加法和减法很简单，它们按分量进行。乘法稍微复杂，因为分配后会产生高达六次的项…… 考虑由半径为1的正十边形的交替顶点构成的正五边形： image 任何围绕原点的正多边形的顶点之和为零： 1 + ζ² + ζ⁴ + ζ⁶ + ζ⁸ = 0 利用 ζ⁵ = -1 的事实，我们可以将其重写为 ζ⁴ = ζ³ - ζ² + ζ - 1 我们可以使用这个恒等式（与所谓的“分圆多项式”有关）将乘法得到的项的次数降低回三次。详细推导有点繁琐，但这里是我最终实现的代码： `` const phi = { a: -1, b: 1, c: 0, d: 1 }; const phiInverse = { a: -1, b: 1, c: 0, d: 0 }; // The ten points of the decahedron. const z0 = { a: 0, b: 0, c: 0, d: 1 }; const z1 = { a: 0, b: 0, c: 1, d: 0 }; const z2 = { a: 0, b: 1, c: 0, d: 0 }; const z3 = { a: 1, b: 0, c: 0, d: 0 }; const z4 = { a: 1, b: -1, c: 1, d: -1 }; const z5 = { a: 0, b: 0, c: 0, d: -1 }; const z6 = { a: 0, b: 0, c: -1, d: 0 }; const z7 = { a: 0, b: -1, c: 0, d: 0 }; const z8 = { a: -1, b: 0, c: 0, d: 0 }; const z9 = { a: -1, b: 1, c: -1, d: 1 }; function sum(x, y) { return { a: x.a + y.a, b: x.b + y.b, c: x.c + y.c, d: x.d + y.d, }; } function difference(x, y) { return { a: x.a - y.a, b: x.b - y.b, c: x.c - y.c, d: x.d - y.d, }; } function product(x, y) { return { a: x.a * y.d + x.b * y.c + x.c * y.b + x.d * y.a + x.a * y.c + x.b * y.b + x.c * y.a, b: x.b * y.d + x.c * y.c + x.d * y.b - (x.a * y.c + x.b * y.b + x.c * y.a), c: x.c * y.d + x.d * y.c - x.a * y.a + (x.a * y.c + x.b * y.b + x.c * y.a), d: x.d * y.d - x.a * y.b - x.b * y.a - (x.a * y.c + x.b * y.b + x.c * y.a), } } function shorten(p) { return product(phiInverse, p); } function midpoint(p, q) { const side = difference(q, p); return sum(p, shorten(side)); } `` 在JS（这个庞大的语言）中，我们缺乏真正的整数类型。所以按照这里的代码写，我们实际上并没有获得精确相等比较的好处。但是，嘿，如果我们想在浏览器中画图，这就是我们不得不面对的，你明白意思就行。 ## 资源 (https://k-monk.org/blog/generating-the-p3-tiling/#resources) 你可以检查本页面以获取用于生成此处图片的源代码。Simon Tatham关于同一主题的优秀文章 (https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/aperiodic-tilings/) 也部分启发我写了这篇文章。*Tilings Encyclopedia* (https://tilings.math.uni-bielefeld.de/) 也是一个有用的参考。如果有任何问题或意见，请给我发电子邮件！