平铺算法/数据结构？

Question

平铺算法/数据结构？

5

我在考虑创建一个程序，让我可以玩或解决 Slitherlink 谜题，例如 krazydad.com 上的谜题。它由 4、5、6、7 和 8 边的瓷砖组成。除了七边形瓷砖外，其他瓷砖似乎具有相同长度的边，连接两个七边形瓷砖之间的边（因此将五边形瓷砖连接到四边形瓷砖）具有约为正常长度的 70% 的边长。如下图所示，八边形被交替的五边形和六边形包围。这些通过六边形的远侧连接到其他图块。连通到五边形顶点的是连接到广场的小线条，然后在广场周围形成两个短边的七边形图形。我认为外边缘是通过省略距离中心太远的瓷砖来定义的。

对于数据结构，我认为需要连接所有节点的图形。我可以让用户单击以在最近的链接上放置实线，并且可以轻松检查循环或过多的线路进入节点。我还需要创建瓷砖并将线路与其相关联，其中内部线路分配给两个瓷砖，但被视为一条线路。

至于设置，我正在考虑手动计算点并定义重复瓷砖的最小集合（1 8、4 5、4 6、4 7 和 1 4），然后将它们放置在一起。放置时，我会检查每个我放置的对象的现有接近点，并在发现时将它们合并。然后，我需要检查重复线路并合并它们。

有没有更简单或更干净的方法来 A）生成平铺或 B）在平铺时合并节点和链接？

- Jason Goemaat

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- andrew cooke · Accepted Answer

一些可能有用的观察：

如果你连接相邻多边形的中心点，就可以得到德劳内三角剖分 (1)。
德劳内三角剖分的对偶图（2）即上述图形（边长略有不同，但如果需要可以进行调整）
这里有一个讨论 (3) 如何从德劳内三角剖分生成图形

将它们综合起来，你可以：

生成平铺的中心点（见下文）
从平铺中心构建德劳内三角剖分（通过连接相邻点）。
找到对偶图以获得所需的图形（寻找对偶应该由良好的图形库支持）。

要生成平铺中心的图案，请取最小集并从中心8开始。对于每个90度的旋转，添加（旋转后的）最小集（除了正在旋转的那个中心点外还要添加一个8），并删除重复项。然后在你添加的8上做同样的操作（可以递归或使用堆栈）。

一旦你有了中心点，我不确定连接相邻点的最佳方法是什么 - 你需要一些有效的方法来生成一组候选项。但这不是一个难题，只是有些棘手（“高级”解决方案可能是四叉树或空间哈希，但简单的分箱可能已经足够）。