平铺算法/数据结构？

Question

我正在考虑创建一个让我玩或解决slitherlink难题的程序,比如krazydad.com.它由4,5,6,7和8面的瓷砖组成.除了七面砖之外的所有瓷砖似乎都具有相同长度的侧面,其中两侧在两个七面砖之间(因此将五面砖连接到四面砖)具有大约正常长度的70%的边.正如您在下图中所看到的,八边形被交替的五边形和六边形包围.它们通过六边形的远侧连接到其他人.连接到五边形的尖端的是较小的线,连接到连接到其他组的方块.然后在正方形周围形成具有两个短边的七边形图形.我认为外边缘是通过省略距离中心太远的瓷砖来定义的.

对于数据结构,我认为我需要一个连接所有节点的图形.我可以让用户单击在最近的链接上放置一个实线,我可以检查循环或太多行很容易进入节点.我还需要创建切片并将线条关联到它们,内线被分配给两个切片,但被视为一条线.

至于设置,我正在考虑手动计算点并定义重复图块的最小集合(1 8,4 5,4 6,4 7和1 4),然后将它们放在彼此旁边.放置时,我会检查我正在放置的每个关闭点,如果找到则合并它们.然后我需要检查重复的行并合并它们.

有没有更简单或更简洁的方法来A)生成平铺或B)在进行平铺时合并节点和链接？

Answer 1

一些可能有帮助的观察结果：

• 如果您连接相邻多边形的中心，您将得到 delaunay 三角剖分 ( 1 )。

• delaunay 三角剖分的对偶 ( 2 ) 是上图（边长略有不同，但您可以根据需要进行调整）

• 这里有一个关于如何从 delaunay 三角剖分生成图形的讨论 ( 3 )

所以，把它们放在一起，你可以：

• 生成图块的中心（见下文）

• 从图块中心构建 delaunay 三角剖分（通过加入邻居）。

• 求对偶得到你想要的图（求对偶的过程应该有好的图库支持）

要生成图块中心的图案，请采用最小集并从中心 8 开始。对于该中心每旋转 90 度，添加（旋转的）最小集（除了要旋转的集之外，还要加上 8），删除重复项。然后对您添加的 8 执行相同操作（递归或使用堆栈）。

一旦你有了这些中心，我不确定连接邻居的最佳方式是什么 - 你需要一些有效的方式来产生一组候选人。但这不是一个难题，只是很麻烦（一个“奇特”的解决方案是四叉树或空间哈希，但只是一个粗略的分箱可能就足够了）。