An Efficient Exhaustive Search Algorithm for the Escherization Problem
An Efficient Exhaustive Search Algorithm for the Escherization Problem
复制标题
一种高效的 Escherization 问题穷举搜索算法
DOI：
10.1007/s00453-020-00695-6
复制
发表时间：
2020
期刊：
影响因子：
1.1
通讯作者：
S. Imahori
中科院分区：
文献类型：
--
作者：
Y. Nagata;S. Imahori
在土方工程化问题中，给定一个平面上的封闭图形，目标是找到一个尽可能接近输入图形的封闭图形，并将平面平铺。小泉和杉原的配方减少了这个问题的特征值问题，其中的瓷砖和输入的数字表示为点多边形。在他们的公式中，相同数量的点被分配给每个瓷砖边缘，形成一个瓷砖模板，以参数化瓷砖形状。通过考虑所有可能的配置的分配点的平铺边缘，我们可以实现很大的灵活性，在可能的瓷砖形状和质量的最佳瓷砖形状大幅提高，在成本巨大的计算工作。在本文中，我们提出了一个有效的算法来找到最佳的瓷砖形状，这个扩展配方的土方化问题。
In the Escherization problem, given a closed figure in a plane, the objective is to find a closed figure that is as close as possible to the input figure and tiles the plane. Koizumi and Sugihara's formulation reduces this problem to an eigenvalue problem in which the tile and input figures are represented as-point polygons. In their formulation, the same number of points are assigned to every tiling edge, which forms a tiling template, to parameterize the tile shape. By considering all possible configurations for the assignment of thepoints to the tiling edges, we can achieve much flexibility in terms of the possible tile shapes and the quality of the optimal tile shape improves drastically, at the cost of enormous computational effort. In this paper, we propose an efficient algorithm to find the optimal tile shape for this extended formulation of the Escherization problem.