29

我有一个 3 维数组。把它想象成一块砖。这块砖有 24 种可能的旋转（保持其边缘平行于坐标轴）。如何生成所有对应的 3 维数组？

4

5 回答 5

19

一个骰子（半对骰子）可以方便地观察 24 个不同的方向，并可以建议生成它们的操作顺序。你会看到六个面中的任何一个都可以在最上面，下面的边可以旋转到四个不同的基本方向。让我们表示两个操作：“<em>turn”和“<em>roll”，其中turn将骰子围绕 z 轴从一个基数旋转到下一个基数，而roll将骰子旋转 90° 远离您，所以离开-face 成为底面，近面成为顶面。这些操作可以使用 Felipe Lopes 的回答中提到的旋转矩阵来表示，或者可以表示为简单的函数，当给定 (x,y,z) 时返回 (-y,x,z) 或 (x,z,- y)，分别。

无论如何，如果您将 1 放在近面、2 放在右侧、3 放在顶部的骰子，您会发现以下步骤顺序会生成 12 个不同的方向，顶部有 1、2 或 3 个点：RTTTRTTTRTTT。然后序列 RTR 暴露 6、4、5，其中 1、2、3 最初是，并且序列 RTTTRTTTRTTT 的重复生成顶部有 4、5 或 6 个点的 12 个方向。提到的序列嵌入在以下 python 代码中。

def roll(v): return (v[0],v[2],-v[1])
def turn(v): return (-v[1],v[0],v[2])
def sequence (v):
    for cycle in range(2):
        for step in range(3):  # Yield RTTT 3 times
            v = roll(v)
            yield(v)           #    Yield R
            for i in range(3): #    Yield TTT
                v = turn(v)
                yield(v)
        v = roll(turn(roll(v)))  # Do RTR

p = sequence(( 1, 1, 1))
q = sequence((-1,-1, 1))
for i in sorted(zip(p,q)):
    print i

打印出已转换点对的排序列表的基本原理是双重的：（i）任何面部方向都可以通过其两个角的位置来指定；(ii) 然后很容易检查每对的唯一性，例如通过管道输出到uniq。

以下是排序输出的开始方式：

((-1, -1, -1), (-1, 1, 1))
((-1, -1, -1), (1, -1, 1))
((-1, -1, -1), (1, 1, -1))
((-1, -1, 1), (-1, 1, -1))
((-1, -1, 1), (1, -1, -1))
((-1, -1, 1), (1, 1, 1))
((-1, 1, -1), (-1, -1, 1))
((-1, 1, -1), (1, -1, -1))
((-1, 1, -1), (1, 1, 1))
于 2013-05-09T17:43:47.820 回答
6

让 X 绕 X 轴旋转 90 度，Y 绕 Y 轴旋转 90 度，那么 24 种可能的唯一组合是（所有可能的组合最多 5 次旋转，除了具有四次相同旋转的组合（例如 XXXX、XXXXY XYYYY 等）：

1.  I
2.  X
3.  Y
4.  XX = YXXY
5.  XY
6.  YX
7.  YY = XYYX
8.  XXX = XYXXY = YXXYX = YXYXY = YYXYY
9.  XXY = YXXYY = YYYXX
10. XYX = YXY
11. XYY = XXYYX = YYXXX
12. YXX = XXYYY = YYXXY
13. YYX = XXXYY = XYYXX
14. YYY = XXYXX = XYXYX = XYYXY = YXYYX
15. XXXY
16. XXYX = XYXY = YXYY
17. XXYY = YYXX
18. XYXX = YXYX = YYXY
19. XYYY
20. YXXX
21. YYYX
22. XXXYX = XXYXY = XYXYY = YXYYY
23. XYXXX = YXYXX = YYXYX = YYYXY
24. XYYYX = YXXXY

当然，您可以使用任意两个 90 度旋转来代替 X 和 Y。例如，Y 和 Z。

或者，如果您还使用 Z，则围绕 Z 轴旋转 90 度，然后旋转 4 次就足够了：

1.  I
2.  X = YXZ
3.  Y = ZYX
4.  Z = XZY
5.  XX = XYXZ = YXXY = YXYZ = YXZX = YYZZ = YZXZ = ZXXZ = ZZYY
6.  XY = YZ = ZX = XZYX = YXZY = ZYXZ
7.  XZ = XXZY = YXZZ = YYYX = ZYYY
8.  YX = XZZZ = YYXZ = ZYXX = ZZZY
9.  YY = XXZZ = XYYX = YZYX = ZXYX = ZYXY = ZYYZ = ZYZX = ZZXX
10. ZY = XXXZ = XZYY = YXXX = ZZYX
11. ZZ = XXYY = XYZY = XZXY = XZYZ = XZZX = YYXX = YZZY = ZXZY
12. XXX
13. XXY = XYZ = XZX = YZZ = ZXZ
14. XXZ = ZYY
15. XYX = YXY = YYZ = YZX = ZXX
16. XYY = YZY = ZXY = ZYZ = ZZX
17. XZZ = YYX
18. YXX = ZZY
19. YYY
20. ZZZ
21. XXXY = XXYZ = XXZX = XYZZ = XZXZ = YZZZ = ZXZZ = ZYYX
22. XXYX = XYXY = XYYZ = XYZX = XZXX = YXYY = YYZY = YZXY = YZYZ = YZZX = ZXXY = ZXYZ = ZXZX = ZYZZ = ZZXZ
23. XYXX = XZZY = YXYX = YYXY = YYYZ = YYZX = YZXX = ZXXX
24. XYYY = YXXZ = YZYY = ZXYY = ZYZY = ZZXY = ZZYZ = ZZZX

这 24 个矩阵都存在三个列向量，每个列向量包含两个零和一个减一或加一。在每一行上也正好有两个零。因此，它们可以很容易地生成：第一列向量有六种可能性（（1,0,0），（-1,0,0），（0,-1,0），（0,1,0） , (0,0,-1) 和 (0,0,1))，这对应于将正 X 轴移动到正或负 x、y 或 z 轴。第二列向量只有四种可能性，因为它必须包含一个零，而第一列的值是非零值。最后，第三列向量只剩下一个可以加或减一的位置。这给出了 6 * 4 * 2 = 48 个矩阵，其中一半也反映了原始矩阵（它们是镜像和可选旋转的组合）。因此只有 24 个是纯旋转。

于 2018-05-26T20:26:02.010 回答
5

您可以使用旋转矩阵。围绕 x 轴旋转 3D 数组意味着 position 处的元素(i,j,k)将被映射到 position (i,-k,j)。当然，如果您的数组是 0 索引的，您可能必须替换-k为size-1-k或类似的东西。

类似地，绕 y 轴旋转映射(i,j,k)到(k,j,-i)。这两个旋转可以表示为矩阵。对于 x 轴旋转：

|i'|   |1  0  0| |i|
|j'| = |0  0 -1|*|j|
|k'|   |0  1  0| |k|

对于 y 轴旋转：

|i'|   |0  0  1| |i|
|j'| = |0  1  0|*|j| 
|k'|   |-1 0  0| |k|

任何一般的旋转都可以描述为这两个旋转的序列。连续应用两次旋转只是将 3x3 矩阵相乘。因此，如果您找到它们的所有可能产品，您将获得 24 个矩阵（包括身份），每个矩阵对应于您的数组的有效旋转。找到所有可能的乘法有点棘手，因为它们不通勤。

我认为你可以暴力破解所有形式(A^p)*(B^q)*(A^r)*(B^s)的乘积，其中 A 和 B 是之前的两个矩阵，p,q,r,s是它们的幂，范围从 0 到 3（将 A 或 B 取幂到 4 会将它们带回单位矩阵） .

这样做，您可以生成所有 24 个有效的旋转矩阵，并使用它们中的每一个旋转 3D 数组，注意移动负索引，以免访问超出范围。

于 2013-05-09T02:19:03.357 回答
5

James Waldby的回答令人鼓舞，我想添加一个稍微改进的版本，只有两个 for 循环。

我们知道有 24 个独特的方向。我通过想象一个骰子来计算：顶面有 6 种可能的选择，顶面的每个面有 4 种可能的旋转。

如果我们用这个想法进行迭代呢？我想。如果我们能找到一种方法来遍历骰子的所有 6 个面，那么我们只需要观察每个面的 4 次旋转，我们就完成了！

所以我抓起最近的“砖块”（在我的例子中是一个维他奶纸盒）并开始旋转，看看什么是最容易访问所有 6 个面孔的模式。如果我们引入一个额外的逆时针转动，那么我们的操作是：

  • 滚动（以固定方向，例如，使面向您的脸现在向下旋转）
  • 顺时针转动（沿固定轴，例如使面向您的面顺时针转动，但仍面向您）
  • 逆时针转动（沿与最后一个相同的轴）

然后我们可以通过以下方式访问所有面孔：

滚动 -> 顺时针转动 -> 滚动 -> 逆时针转动 -> 滚动 -> 顺时针转动 -> 滚动 -> 逆时针转动 -> 滚动 -> 顺时针转动 -> 滚动 -> 逆时针转动

随着最后的滚动和转弯，我们又回到了原来的方向。如您所见，它是滚动 + 交替 CW 转弯和 CCW 转弯的重复序列。

现在，如果我们将其扩展为包括我们访问的每个面的所有旋转，则变为：

滚动 -> 3x 顺时针转动 -> 滚动 -> 3x 逆时针转动 -> 滚动 -> 3x 顺时针转动 -> 滚动 -> 3x 逆时针转动 -> 滚动 -> 3x 顺时针转动 -> 滚动 -> 3x 逆时针转动

...我们又回到了开始的地方！这可以转化为两个 for 循环（少一个！）：

def sequence(m):
  for roll_index in range(6):
    m = roll(m)
    yield(m)
    for turn_index in range(3):
      m = turn_cw(m) if roll_index % 2 == 0 else turn_ccw(m)
      yield(m)
于 2019-10-20T08:49:46.297 回答
2 
import numpy as np

def rotations(array):
    for x, y, z in permutations([0, 1, 2]):
        for sx, sy, sz in itertools.product([-1, 1], repeat=3):
            rotation_matrix = np.zeros((3, 3))
            rotation_matrix[0, x] = sx
            rotation_matrix[1, y] = sy
            rotation_matrix[2, z] = sz
            if np.linalg.det(rotation_matrix) == 1:
                yield np.matmul(rotation_matrix, array)

all_rotations = list(rotations(np.array(array)))

想法是生成具有可能轴方向变化的所有坐标重新标记，例如。(-z, y, x)。剩下的问题是是否所有坐标重新标记都可以仅使用旋转从 (x, y, z) 轴获得。6 * (2^3) = 48 个标签中的一半不是因为它们是 (x, y, z) 坐标的镜像版本的旋转（左手坐标，https: //en.wikipedia.org/ wiki/Right-hand_rule )。

重标记操作的相应旋转矩阵A的行将在每一行中只有一个值。该值确定要在该索引上选择哪个轴，以及是否翻转轴。

A * (x, y, z) = (-z, y, x)

    | 0, 0, -1 |
A = | 0, 1, 0  |
    | 1, 0, 0  |

我们只保留那些旋转，这det(A) == 1意味着操作只应用了旋转。det(A) == -1表示它是带镜像的旋转。

于 2021-12-19T16:47:16.910 回答