下面这个动画是受到

Finding Ellipses: What Blaschke Products, Poncelet’s Theorem, and the Numerical Range Know about Each Other

这本书启发所作：

我昨晚刚完成了一个 Shadertoy 小动画，演示平面几何中的 Marden 定理、复分析中的 Gauss-Lucas 定理 以及静电场的关系：

周末刚完成了一个有点烧脑的 Shadertoy 项目，Escher 风格的 非周期密铺：

和之前一样，我们还是通过一个有趣的问题来引入主题。

问题：在 \(n\times n\) 的正方形网格图 \(G_n\) 的所有生成树中等概率地随机任选一个，记这个随机生成树为 \(T\)，\(T\) 叫做 \(G_n\) 的一个均匀生成树。对 \(G_n\) 中任一顶点 \(v\)，\(v\) 是 \(T\) 的叶节点的概率是多少？

这个问题可以换一种更通俗的描述：

等价问题：对一个完全随机的 \(n\times n\) 的完美迷宫，它包含的“死角”的比例是多少？

为什么这两个问题是一回事？

一个迷宫称作是完美的，如果迷宫中的任何两个房间之间都有且仅有唯一的道路相连，这正是生成树的等价描述！迷宫中的一个房间称作是“死角”，当且仅当它只有一条道路与其它房间相通，没有其它出路，这正是叶节点的等价描述！

下图显示了三个不同的均匀生成树，它们分别来自大小为 \(80\times 80\)，\(120\times120\) 和 \(200\times200\) 的三个网格图，这三个生成树的叶节点（用蓝色标出）占全体顶点的比例分别为 \(1884/6400=0.294375\)，\(4234/14400\approx0.294028\)，\(11776/40000=0.2944\)。咦？看起来好像是在围着一个固定的值波动喔？

更新：由于使用 POV-Ray 渲染三维双曲蜂巢非常的慢，所以我放弃了这种途径，并将代码从 Github 主分支中移除。你可以在 旧存档 中找到本文使用的代码。关于怎样渲染双曲蜂巢读者可以参考 另一个项目。

本文介绍我刚刚完成的一个 Python 程序。虽然是刚刚完成，但是它占去了我这半年来大部分的业余时间，也算是一个艰苦攻关，呕心沥血之作。主要是它涉及的理论比较复杂，要用到 Coxeter 群的一些深刻的性质，即所谓的 automatic property。这半年里面不少时间是花在学习 Casselman 和 Brink & Howlett 等人的文章上面，这才弄懂了其中的数学原理（见参考文献）。

虽然完成这个程序很有成就感，但是我无意强调这个程序的任何优越性：它采用的 Coxeter 群的计算方法并不先进，难入行家的法眼。而且它的代码比较丑，大概率除了我，别人也很难用起来。

这个程序的目的是使用群论的方式来绘制二维和三维的各种 均匀密铺。所谓均匀密铺，你可以理解为用一些正多边形的瓷砖密铺整个空间，使得瓷砖的顶点在对称群作用下是传递的（构成单一轨道）。

我先展示一些这个程序的例子，然后介绍它的实现原理。