2D 矩阵上的移位、旋转和翻转操作可以组合成一个操作吗？

Question

这个问题在这里已经有了答案:





C++/OpenGL convert world coords to screen(2D) coords

(1 个回答)


4年前关闭。




假设我有一个 n x n 矩阵，其中每个单元格为 0 或 1。有一个输入程序的命令列表。这些命令指定一个操作(移位、旋转、翻转)和一个值 x，以指定操作的幅度。该操作只会移动其中包含 1 的单元格。 “UP 3”操作将导致所有带有“1”的单元格向上移动 3。

在有多个操作必须顺序应用于矩阵的情况下，为了优化，我可以做的是组合相同类型的连续操作。如 (up, down, left, right) 都是相同的类型 (shift)。 CW 和 CCW 旋转将是相同的类型。并且在 x 或 y 方向上翻转将是相同的类型。如果它们一个接一个地发生，我可以组合多个相同类型的操作。 (即 UP 3，DOWN 2 -> 导致净 UP 1)。我想知道是否有一种方法可以通过组合 的操作来执行单个“网络”操作不同类型。

所以我想知道，在我的操作列表中，如果我有例如 1 UP、1 CW、3 RIGHT、1 Y FLIP、2 DOWN。

不是在 6 个“ Action ”中执行上述 6 条指令，而是有一种数学/编程方式将它们组合成 单 n x n 矩阵的指令？

必须在 C 中可行。

Answer 1

在评论中，术语有些困惑，所以让我们澄清一下这些术语。

假设您有一组九个独特的操作:UP , DOWN , LEFT , RIGHT , ROTATE+90 , ROTATE+180 , ROTATE+270 , HFLIP , 和 VFLIP .您已将这些中的每一个实现为单独的函数，将 N×N 矩阵的内容复制到新矩阵。

(另请注意，您不能在只有一个和零的矩阵中移动、旋转或翻转/镜像“只有一个”。如果您尝试，效果与将操作应用于 1 和 0 时的效果相同。试试看，你会看到的。)

如果我理解正确，这个问题可以重述为

Is there a way to combine any sequence of those operations, so that I only need one double loop, rather than a double loop for each individual operation?

答案是肯定的，但是实现起来很棘手，并且移位( UP 、 DOWN 、 LEFT 、 RIGHT )可以通过两种不同的方式进行操作，具体取决于“移出”的元素是否出现从另一个边缘，或丢失。例如，考虑 RIGHT对 4×4 矩阵的操作:

Horizontally periodic        nonperiodic
 0 0 1 0     0 0 0 1     0 0 1 0     0 0 0 1
 0 1 1 1  ⇒  1 0 1 1     0 1 1 1  ⇒  0 0 1 1
 0 0 1 0     0 0 0 1     0 0 1 0     0 0 0 1
 0 0 0 0     0 0 0 0     0 0 0 0     0 0 0 0

矩阵可以是非周期性的、水平周期性的、垂直周期性的或完全周期性的(即，水平和垂直周期性)。

为简单起见，让我们假设非周期性边界:如果它们移动到矩阵之外，它们就会丢失。零总是“移入”。 (这是最简单的情况。)

九个独特操作的任意组合，以任何顺序，甚至重复，都可以使用单个双循环来实现:

For newrow = 1 to N:
    row = oldrow
    col = oldcol
    For newcol = 1 to N:
        If (row >= 1) and (row <= N) and
           (col >= 1) and (col <= N) and
           (oldmatrix[row][col] == 1):
            newmatrix[newrow][newcol] = 1
        Else:
            newmatrix[newrow][newcol] = 0
        End if
        row = row + colsteprow
        col = col + colstepcol
    End For
    oldrow = oldrow + rowsteprow
    oldcol = oldcol + rowstepcol
End For

正如我所说，这有点棘手。考虑叠加新旧矩阵，但应用操作序列，并将旧矩阵(行号和列号)扩展到无穷大。 (因此，旧矩阵中的行数和列数不再限制为 1..N，而是可以是任意整数。)

您需要识别对应于新矩阵中的三个元素的行号和列号(在旧矩阵中):第一行中的第一列、第一行中的第二列和第二行中的第一列.

让 row11和 col11识别旧的无限矩阵中与新矩阵的第一列第一行重合的元素； row12和 col12与新矩阵中第二列第一行重合的元素；和 row21 , col21与新矩阵中第一列第二行重合的元素。

(换句话说，您只需要跟踪您的操作如何重新定位/旋转/镜像旧矩阵中的这三个单元格。提示:反向。)

然后，在上述伪代码的开头，设置oldrow = row11 , oldcol = col11 , colsteprow = row12 - row11 , colstepcol = col12 - col11 , rowsteprow = row21 - row11 , 和 rowstepcol = col21 - col11 .

本质上，colsteprow和 colstepcol形成一个整数 vector ，告诉我们新矩阵中列号的增量如何对应于旧矩阵中行和/或列的变化。 (其中一个始终为零，另一个为 +1 或 -1。)

同样，rowsteprow和 rowstepcol告诉我们新矩阵中行号的增加如何对应于旧矩阵中行号和/或列号的变化。

如果你的矩阵是水平周期性的，那么你换行 oldcol == 0至oldcol = N , 和 oldcol == N+1至oldcol == 1 , 并删除 oldcol 的 If 检查.同样，如果您的矩阵是垂直周期性的，那么您可以换行 oldrow == 0至oldrow = N , 和 oldrow == N+1至oldrow = 1 ，然后您放弃 oldrow 的 If 检查.

如果你很难理解它是如何工作的，拿一张透明的东西，在上面画一个小网格，用行号和列号标记每个单元格。在纸上画一个小矩阵，单元格大小相同。这些操作移动、旋转和镜像纸张顶部的透明纸。实验和观察。