Two algorithms for randomly generating aperiodic tilings
a day ago
- 罗杰·彭罗斯发现了使用两种瓷砖类型的非周期性铺砌（P2、P3）；2023年发现了一种单一的“帽子”瓷砖，通过反射强制产生非周期性。
- 这些铺砌可以通过按照固定规则用更小的瓷砖替换每个瓷砖来递归生成，通常使用中间瓷砖系统（半瓷砖或元瓷砖）。
- 比较了两种主要算法：（1）从固定大块进行递归扩展，该方法简单但对于帽子铺砌由于几何变形而效率低下；（2）使用每个瓷砖元素的标签序列的组合坐标。
- 组合坐标允许通过操作标签在相邻瓷砖之间移动，无需几何计算，避免了变形问题，并实现了精确的概率分布。
- 对于彭罗斯铺砌，半瓷砖三角形被标记；对于帽子铺砌，使用帽子形状底层的风筝网格，通过重叠元瓷砖扩展来简化导航。
- 组合方法提供了从极限分布中均匀随机采样，无需手动调整，近线性时间，以及低内存使用。
- 精确算术（使用带有黄金比例的复数）避免了两种实现中顶点坐标的浮点误差。
- 作者倾向于在新实现中使用组合坐标，已在Loopy中用于帽子铺砌，并建议如果不是为了向后兼容，也将其用于彭罗斯铺砌。