How to calculate all 24 rotations of 3d array?

I have a 3d numpy array describing a polycube (imagine a 3d tetris piece). How can I calculate all 24 rotations?

Numpy's array manipulation routines includes a rot90 method, which gives 4 of the 24, but I'm clueless how to calculate the rest. My only idea is to convert the 3d array to a 2d matrix of co-ordinates, multiply by a rotation matrix, and convert back. But I'd rather work directly with the 3d array.

Example 2x2x2 array:

>>> from numpy import array
>>> polycube
array([[[1, 0],
        [1, 0]],

       [[1, 1],
        [0, 0]]])

Example 3x3x3 array:

array([[[1, 1, 0],
        [1, 1, 0],
        [0, 0, 0]],

       [[0, 0, 0],
        [1, 0, 0],
        [1, 0, 0]],

       [[0, 0, 0],
        [0, 0, 0],
        [0, 0, 0]]])

Edit: I only want the 24 orientation-preserving isometries, not all 48 rotations and reflections (though it would be interesting to know how to make them too). If it helps to test, I believe the 3x3x3 example has no rotational symmetry and is chiral (so the 48 are distinct).

Motivation: I'm writing a solver for a Soma cube-style puzzle.

Look at the code for rot90. I see 3 variations on flip and swapaxes, depending on k the axis parameter.

fliplr(m).swapaxes(0, 1)
fliplr(flipud(m))
fliplr(m.swapaxes(0, 1))

fliplr(m) is just m[:, ::-1], and not surprisingly, flipud is m[::-1, ...].

You could flip the 3rd axis with m[:,:,::-1], or m[...,::-1].

np.transpose is another tool for permuting axes, that may, or may not, be easier to use than swapaxes.

If rot90 gives you 4 of the rotations, you should be able apply the same routines to produce the others. You just have to understand the logic underlying rot90.

e.g.

def flipbf(m):
    return m[:,:,::-1]

flipbf(m).swapaxes(0, 2)
flipbf(m).swapaxes(1, 2)
etc

Rotation matrix, 3D Rotations: SO(3)¶. The group of all rotations in the 3D Cartesian space is called SO(3) . The most practical representation of orientation is a rotation matrix We can easily convert rotation matrices between the two conventions by transposing them. We can There are 24 different conventions for defining euler angles. This tutorial introduces how to rotate objects in 3D beyond Euler angles; to do this, it looks at the basics of matrices and quaternions. What follows is math heavy, so a robust artistic

So far I have 12 of them, composing numpy.transpose to permute the axes (xyz, yzx, zxy—all the same handedness) and rot90.

def rotations12(polycube):
    for i in range(3):
        polycube = numpy.transpose(polycube, (1, 2, 0))
        for angle in range(4):
            polycube = numpy.rot90(polycube)
            yield polycube

Quick test the 12 are distinct: len(set(str(x) for x in rotations(polycube)))


Update: here's how I made all 24.

def rotations24(polycube):
    # imagine shape is pointing in axis 0 (up)

    # 4 rotations about axis 0
    yield from rotations4(polycube, 0)

    # rotate 180 about axis 1, now shape is pointing down in axis 0
    # 4 rotations about axis 0
    yield from rotations4(rot90(polycube, 2, axis=1), 0)

    # rotate 90 or 270 about axis 1, now shape is pointing in axis 2
    # 8 rotations about axis 2
    yield from rotations4(rot90(polycube, axis=1), 2)
    yield from rotations4(rot90(polycube, -1, axis=1), 2)

    # rotate about axis 2, now shape is pointing in axis 1
    # 8 rotations about axis 1
    yield from rotations4(rot90(polycube, axis=2), 1)
    yield from rotations4(rot90(polycube, -1, axis=2), 1)

def rotations4(polycube, axis):
    """List the four rotations of the given cube about the given axis."""
    for i in range(4):
        yield rot90(polycube, i, axis)

Using this helper function generalising rot90 to rotate about any axis:

def rot90(m, k=1, axis=2):
    """Rotate an array k*90 degrees in the counter-clockwise direction around the given axis"""
    m = numpy.swapaxes(m, 2, axis)
    m = numpy.rot90(m, k)
    m = numpy.swapaxes(m, 2, axis)
    return m

I'm not confident this helper is perfect, but it seemed to work.

3D Rotations: SO(3), The most general three-dimensional rotation matrix represents a counterclockwise To determine the rotation angle θ, we note that the properties of the trace imply over any pair of repeated indices in the present and all subsequent formulae. (24) it follows that. 2nm sin θ = −Rijǫijm . (25). If R is a symmetric matrix (i.e.  Rotating in three dimensions. We can now rotate our cube in two dimensions, but it still looks like a square. What if we want to rotate our cube around the y-axis (veritcal axis). If we imagine looking down on our cube as we rotate it around the y-axis, what we would see is a rotating square, just like we do when we rotate about the z-axis.

Edit: As my solution basically boils down to the product of the parities of the axes multiplied by the parity of the permutation of the axes, the simplest method for generating all of the regular rotations of an n-dimensional array is this (swiping some code form @Divakar's answer):

import itertools as it

def p_parity(a):
    a = np.asarray(a)
    l = a.size
    i, j = np.tril_indices(l, -1)
    return np.product(np.sign(a[i] - a[j]))

def rotations_gen(m):
    n = m.ndim
    for i in it.product([-1, 1], repeat = n):
        for p in it.permutations(np.arange(n)):
            if np.product(i) * p_parity(p) == 1:
                s = [slice(None, None, j) for j in i]
                yield np.transpose(m[s], p)    

This works for any (even non-square) tensors of arbitrary dimension and is based directly on the definition of regular rotations under tensor algebra below.

Background

Easiest way to explain this is in tensor terms, so lets turn all those rotations into rotation tensors. Rotation tensors are n x n matrices that rotate an n-dimensional space. As such they have a few properties:

np.linalg.det(R) == 1                    # determinant = 1
np.inner(R, R.T) == np.eye(R.shape[0])   # Transpose is inverse

In addition, for 90 degree roatations all terms must be either 0, 1, or -1.

In three dimensions, there are three basic families of these, which compose togther to make your 24 rotations.

The first is simple permutation:

A = 
[[[1, 0, 0],
  [0, 1, 0],
  [0, 0, 1]],

 [[0, 1, 0],
  [0, 0, 1],
  [1, 0, 0]],

 [[0, 0, 1],
  [1, 0, 0],
  [0, 1, 0]]]

The second involves negating some terms so that the product of the diagonal is always 1:

B = 
[[[ 1, 0, 0],
  [ 0, 1, 0],
  [ 0, 0, 1]],

 [[-1, 0, 0],
  [ 0,-1, 0],
  [ 0, 0, 1]],

 [[-1, 0, 0],
  [ 0, 1, 0],
  [ 0, 0,-1]],

 [[ 1, 0, 0],
  [ 0,-1, 0],
  [ 0, 0,-1]]]

And the third determines whether the permutation is positive or negative, and negates the terms if negative

C = 
[[[ 1, 0, 0],
  [ 0, 1, 0],
  [ 0, 0, 1]],

 [[ 0, 0,-1],
  [ 0,-1, 0],
  [-1, 0, 0]],

The imprtant thing about these families is in each family any product, power or transpose of two matrices yields another matrix in the family. Since we have three families, their products with each other form all the possible rotations, in this case 3*4*2 = 24

Note: the other 24 "irregular" rotations are the same matrices multiplied by -np.eye(3) which yeild similar matrices with determinant = -1

Application

That's all well and good, but how does that relate to array manipulation? We don't want to rotate by matrix multiplication, as that will cause undue overhead in memory and processing. Luckily, each family is easily related to a an array manipulation that produces a view.

def A_(m, i):  # i in (0, 1, 2)
    idx = np.array([[0, 1, 2], [1, 2, 0], [2, 0, 1]])
    return np.transpose(m, idx[i])

def B_(m, j):  # j in (0, 1, 2, 3)
    idx = np.array([[ 1, 1, 1],
                    [ 1,-1,-1],
                    [-1, 1,-1],
                    [-1,-1, 1]])
    return m[::idx[j, 0], ::idx[j, 1], ::idx[j, 2]]

def C_(m, k):  # k in (1, -1)
    return np.transpose(m, np.arange(3)[::k])[::k, ::k, ::k]

All of these produce views of m, and you can create a generator that produces views relating to all of the rotations by:

def cube_rot_gen(m):
    for i in [0, 1, 2]:
        for j in [0, 1, 2, 3]:
            for k in [1, -1]:
                yield C_(B_(A_(m, i), j), k)

[PDF] Three-Dimensional Rotation Matrices, This video is part of an online course, Interactive 3D Graphics. Check out the course here: https Duration: 3:02 Posted: Feb 23, 2015 This calculator is the "rotation of axes" Calculator.If you rotate the point, please use the "rotation of points" Calculator. 2018/03/12 07:02 Male/Under 20 years old/High-school/ University/ Grad student/A little /

Another option is to combine the rotations around the axis of the cube that represents the matrix. Something like:

import numpy as np


"""
Basic rotations of a 3d matrix.
----------
Example:

cube = array([[[0, 1],
               [2, 3]],

              [[4, 5],
               [6, 7]]])

axis 0: perpendicular to the face [[0,1],[2,3]] (front-rear)
axis 1: perpendicular to the face [[1,5],[3,7]] (lateral right-left)
axis 2: perpendicular to the face [[0,1],[5,4]] (top-bottom)
----------
Note: the command m[:, ::-1, :].swapaxes(0, 1)[::-1, :, :].swapaxes(0, 2) rotates the cube m
around the diagonal axis 0-7.
"""


def basic_rot_ax(m, ax=0):
    """
    :param m: 3d matrix
    :return: rotate the cube around axis ax, perpendicular to the face [[0,1],[2,3]]
    """

    ax %= 3

    if ax == 0:
        return np.rot90(m[:, ::-1, :].swapaxes(0, 1)[::-1, :, :].swapaxes(0, 2), 3)
    if ax == 1:
        return np.rot90(m, 1)
    if ax == 2:
        return m.swapaxes(0, 2)[::-1, :, :]


def axial_rotations(m, rot=1, ax=2):
    """
    :param m: 3d matrix
    :param rot: number of rotations
    :param ax: axis of rotation
    :return: m rotate rot times around axis ax, according to convention.
    """

    if len(m.shape) is not 3:
        assert IOError

    rot %= 4

    if rot == 0:
        return m

    for _ in range(rot):
        m = basic_rot_ax(m, ax=ax)

    return m

If I am not wrong, the 24 rotations you are looking for are a combination of these 9 transformations.

Rotation Matrix - Interactive 3D Graphics, June 2019. 3D Rotations. 5. Way 1: 3x3 matrix (9 floats). ○ after all, each rotation is a linear matrix. ○ (3x3 submatrix of the 4x4 rotation matrix). ○ as we know  Circular rotation of an array using deque in C++; Block swap algorithm for array rotation; Left Rotation and Right Rotation of a String; Print left rotation of array in O(n) time and O(1) space; Find the Rotation Count in Rotated Sorted array; Maximum number by concatenating every element in a rotation of an array

We would start off with the intention of getting all 48 combinations so that we get the general idea about solving it for a n-dim array. Later on we would filter out the unwanted 24 ones.

Generic idea to solve for all rotations

The idea to solve for a generic case would be to basically do two things - flip along every axis and permute axes with all combinations for the given number of axes.

Flip : To flip, we would use the stepsize parameter for slicing, i.e. array[::stepsize]. So, to flip, it would be : [::-1] and without flipping, simply : [::1]. That stepsize could be assigned as a variable varying between 1 and -1 for the two combinations simpl. For a ndarray, simply extend this to all axes.

Permute axes : To achieve this, we can use np.transpose and specify the required permuted order as the axes parameter with it. We will generate all possible orders with itertools.permutations.

That's all there is! Let's implement it with a as the input 3D array -

import itertools

def rotations48(a):
    # Get all combinations of axes that are permutable
    n = a.ndim
    axcomb = np.array(list(itertools.permutations(range(n), n)))

    # Initialize output array
    out = np.zeros((6,2,2,2,) + a.shape,dtype=a.dtype)

    # Run loop through all axes for flipping and permuting each axis
    for i,ax in enumerate(axcomb):
        for j,fx in enumerate([1,-1]):
            for k,fy in enumerate([1,-1]):
                for l,fz in enumerate([1,-1]):
                    out[i,j,k,l] = np.transpose(a[::fx,::fy,::fz],ax) 
    return out

We could simplify for the flipping nested loops with one loop -

def rotations48(a):
    n = a.ndim
    axcomb = list(itertools.permutations(range(n), n)) # all axes combinations    
    pcomb = list(itertools.product([1,-1], repeat=n)) # all permuted orders
    out = np.zeros((6,8,) + a.shape,dtype=a.dtype) # Initialize output array    
    for i,ax in enumerate(axcomb): #loop through all axes for permuting
        for j,(fx,fy,fz) in enumerate(pcomb): # all flipping combinations
            out[i,j] = np.transpose(a[::fx,::fy,::fz],ax) 
    return out

So, this gets us all the 48 combinations.

Extend to more dimensions : If we want to extend this to a 4D array, simply edit the initialization part to extend by 2 and slice along one more axis.


Solve for 24 rotations

Now, as OP is claiming to have a working solution to get the desired 24 combinations, we need to filter out from our proposed solution. I couldn't find a generic pattern for the filtering, but got the indices required for indexing -

idx = np.array([ 0,  3,  5,  6,  9, 10, 12, 15, 17, 18, 20, 23, 24, \
                27, 29, 30, 32, 35, 37, 38, 41, 42, 44, 47])

If you care about the order to have the output same output as with rotations24, we would have -

idx = np.array([ 0, 10,  3,  9,  5, 15,  6, 12, 41, 27, 42, 24, 44, \
                30, 47, 29, 18, 35, 17, 32, 20, 37, 23, 38])

Hence, get the required 24 ones with indexing -

final_out = out.reshape(48,-1)[idx]

This works for 3D arrays with any generic lengths.

Sample run for verification

# From https://stackoverflow.com/a/33190472/ @Colonel Panic
def rotations24_array(a):
    out0 = np.zeros((6,2,2,2,) + a.shape,dtype=a.dtype)    
    p = [list(i) for i in rotations24(a)]
    out0 = np.zeros((6,4,m,m,m),dtype=a.dtype)
    for i in range(6):
        for j in range(4):
            out0[i,j] = p[i][j]   
    return out0

Verify -

In [486]: # Setup    
     ...: np.random.seed(0)
     ...: m = 3
     ...: a = np.random.randint(11,99,(m,m,m))
     ...: 
     ...: # Verify results
     ...: idx = np.array([ 0, 10,  3,  9,  5, 15,  6, 12, 41, 27, 42, 24, 44, \
     ...:                 30, 47, 29, 18, 35, 17, 32, 20, 37, 23, 38])
     ...: out1 = rotations24_array(a).reshape(-1,m**3)
     ...: out2 = rotations48(a).reshape(48,-1)[idx]
     ...: print np.allclose(out1, out2)
True

[PDF] Rotations Representations 3D rotations: how many , in the rotated coordinate system are now given by a rotation matrix which is the Equation (15) is the identity which gives the orthogonal matrix its name. All eigenvalues are 1. det(A)=1,. (24) Using Eigenvalue Analysis to Rotate in 3D​. I need help with rotation of degrees [3] 2019/02/21 07:45 Female / Under 20 years old / Elementary school/ Junior high-school student / Useful / Purpose of use

Rotation Matrix -- from Wolfram MathWorld, ndarray.flatten ([order]), Return a copy of the array collapsed into one dimension. atleast_1d (\*arys), Convert inputs to arrays with at least one dimension. rot90 (m[, k, axes]), Rotate an array by 90 degrees in the plane specified by axes. How to find address of an element in array in Binary Let's say we have an array of 5 elements. Array index starts from 0 Base address of Array = 100 size of each element is 2 ie it's an int array Now we want to find the 2nd element ie A[2].

Array manipulation routines, The set of all rotation matrices forms a group, known as the rotation group or the If the 3D space is right-handed, this rotation will be counterclockwise for an matrix a rotation axis and an angle, and these completely determine the rotation. When we include the option of world axes or body axes, 24. The rotation is performed clockwise, if you are looking along the direction of the rotation axis vector. For counterclockwise rotation, enter negative rotation angle values. Results are rounded up to 6 decimal places. To calculate the angle between two vectors, enter the vector coordinates in the table below.

[PDF] Rotation matrix, in the same way as the product of two rotation matrices gives us the matrix in all methods that compute the quaternion corresponding to a rotation matrix: they all taken as a distance between any two elements of the 3D rotation group SO(​3) matrix using Shepperd's method is about 24%, while using our method this. In fact, it does not make sense to say that at all. The gimbal lock problem happens when you use Euler Angles, which are simply a set of 3 elemental rotations to allow you to describe any orientation in a 3D space. In attitude determination, we often visualize a 3D rotation as a combination of yaw, pitch and roll.

Comments
  • You could use the fliplr and flipud methods to generate the other rotations, in combination with the rot90, I believe
  • Maybe. fliplr and flipud are orientation-reversing so I know I can't use them on their own. I only want the orientation-preserving isometries (24 not 48).
  • Just as a mental exercise: it's important to note how this is different from a more common notion of "3D rotation". Usually, you would take an array of N 3D point points (Nx3 matrix) and multiply it by a 3D rotatin matrix (3x3 matrix), getting as a result another Nx3 matrix, where each column would be the former column (a single 3D point) rotated. What is being asked is quite different, since the original matrix is MxNxO (three axis instead of one or two from the more common case).
  • Numpy 1.12.0 added an axes argument to the rot90 function which may simplify some of the code below
  • I'm not sure flipping/mirroring something should count as a proper 3D rotation, since it changes chirality
  • (Well, unless of course you compose flipping and swapping as you did. Clever!)
  • That could be. I'm assuming the OP knows what he's doing when using rot90.