正方形瓷砖合并算法

我有一个8x8方形板，其上可以有不同颜色的正方形瓷砖的任意组合。这些方形瓷砖可以具有不同的尺寸，我们可以具有从1到8的边的正方形，由于电路板的尺寸，8是最大值。正方形瓷砖合并算法

我需要找到一种算法，使我可以用区域本身的方形瓷砖替换相同颜色的方形区域。

见下面的例子：

Click here to see an example

在这些例子中，我们正在改变标有“x”至黄色瓷砖的颜色，以获得一个更大的方黄色区域。我正在寻找一种算法，它将用与区域本身尺寸相同的相应图块替换大黄色方块区域（步骤C）。也许该算法可以开始检查从我们改变颜色（使用'x'标记的颜色）的瓦片开始的相邻瓦片。

来源

2013-07-14 Francesco

这让我想起八叉树数据结构。 – delnan

如果平铺X是另外两个单色正方形的拐角相交，该怎么办？ –

@DavidEisenstat好的问题，我猜想哪个瓷砖群将“合并”可以随机确定，也可以根据群集的总大小（即较大的群集合并成一个瓷砖）确定。 – Francesco

有了这么小的板子，也许我们可以用蛮力。按照大小的降序循环遍历可能的正方形。

for (int width = 8; width > 0; width--) { 
    for (int x0 = 0; x0 <= 8 - width; x0++) { 
     for (int y0 = 0; y0 <= 8 - width; y0++) { 
      int x1 = x0 + width; 
      int y1 = y0 + width; 
      ... 
     } 
    } 
}

对于每个现有方S，测试候选方[x0, x1] * [y0, y1]是否相交S，并且如果是这样，它是否包含S.若S相交，但不包含，那么[x0, x1] * [y0, y1]不是可能的替换。如果包含S但颜色错误，则同上。

如果候选人在这些测试中存活（并且包含更改后的正方形，以防原始棋盘具有比应该更多的贴图），则将其放置，并删除其包含的正方形。

来源

2013-07-14 22:22:10

感谢这个解决方案大卫，我可以理解底层的逻辑，它非常有意义，我只需要弄清楚确切的数学方法来确定候选方块是否相交并且包含一个现有的方块，我就是肯定是一个非常简单的计算，但没有碰到它之前，我将不得不深入研究它[感觉非常愚蠢！] – Francesco

@Francesco为了测试[x0'，x1'] * [y0'，y1']包含，测试x0 <= x0'和x1'<= x1且y0 <= y0'且y1'<= y1。正方形的交点比较复杂，但应该回答。 –

谢谢，这有帮助，我可以从那里确定交集。 – Francesco

正方形瓷砖合并算法

回答

相关问题