How can I rotate a 2d array by LESS than 90°, to the best approximation?

Question

Say I have an array that is stored in 0° rotation:

And I want it returned in a good approximation if I pass, for example 30° as parameter, it would be something like:

45° would be

I am aware of the solutions posted for 90° rotations. But I don't think that will help me here?

I don't have any examplecode because I currently wouldn't even know where to start looking. If there are any keywords I can google that point me in the directions of some formula I can adapt for this, that would also be great.

Spectre's code solution in C#:

    class Rotation
{

    public Rotation() {
        A = new int[xs,ys]{
{0,0,0,9,0,0,0},
{0,0,0,9,0,0,0},
{0,0,0,9,0,0,0},
{9,9,9,9,0,0,0},
{0,0,0,0,0,0,0},
{0,0,0,0,0,0,0},
{0,0,0,0,0,0,0},
};
        B = new int[xs, ys];

        deg = (float)(Math.PI / 180.0);
    }

    public const int xs = 7; // matrix size
    public const int ys = 7;
    const int x0 = 3; // rotation center cell
    const int y0 = 3;
    readonly float deg; 
    public int[,] A;
    public int[,] B;

    //---------------------------------------------------------------------------

    public void rotcv(float ang) {
        rotcw(Rotation.x0, Rotation.y0, ang);
    }
    private void rotcw(int x0, int y0, float ang) // rotate A -> B by angle ang around (x0,y0) CW if ang>0
    {
        int x, y, ix0, iy0, ix1, iy1, q;
        double xx, yy, fx, fy, c, s;
        // circle kernel
        c = Math.Cos(-ang); s = Math.Sin(-ang);
        // rotate
        for (y = 0; y < ys; y++)
            for (x = 0; x < xs; x++)
            {
                // offset so (0,0) is center of rotation
                xx = x - x0;
                yy = y - y0;
                // rotate (fx,fy) by ang
                fx = ((xx * c) - (yy * s));
                fy = ((xx * s) + (yy * c));
                // offset back and convert to ints and weights
                fx += x0; ix0 = (int)Math.Floor(fx); fx -= ix0; ix1 = ix0 + 1; if (ix1 >= xs) ix1 = ix0;
                fy += y0; iy0 = (int)Math.Floor (fy); fy -= iy0; iy1 = iy0 + 1; if (iy1 >= ys) iy1 = iy0;
                // bilinear interpolation A[fx][fy] -> B[x][y]
                if ((ix0 >= 0) && (ix0 < xs) && (iy0 >= 0) && (iy0 < ys))
                {
                    xx = (A[ix0,iy0]) + ((A[ix1,iy0] - A[ix0,iy0]) * fx);
                    yy = (A[ix0,iy0]) + ((A[ix1,iy0] - A[ix0,iy0]) * fx);
                    xx = xx + ((yy - xx) * fy); q =(int) xx;
                }
                else q = 0;
                B[x,y] = q;
            }
    }
}

test:

 static void Main(string[] args)
    {
        Rotation rot = new Rotation();

        for (int x = 0; x < Rotation.xs; x++) {
            for (int y = 0; y < Rotation.xs; y++) {
                Console.Write(rot.A[x,y] + " ");
            }
            Console.WriteLine();
        }
        Console.WriteLine();
        float rotAngle = 0;
        while (true)
        {
            rotAngle += (float)(Math.PI/180f)*90;
            rot.rotcv(rotAngle);
            for (int x = 0; x < Rotation.xs; x++)
            {
                for (int y = 0; y < Rotation.xs; y++)
                {
                    Console.Write(rot.B[x, y] + " ");
                }
                Console.WriteLine();
            }
            Console.WriteLine();
            Console.ReadLine();
        }

    }

your "approximation" doesn't make sense. there can be cases where the rotation can be approximated to different results. — Juvanis, Nov 14 '16 at 08:48
@Juvanis that's why I said 'something like' it doesn't have to be exactly like the example I gave, that was just to give the idea of what I am trying to do — user3488765, Nov 14 '16 at 08:49
... and that could lead to a permanent loss of value if you really rotate the array. — AxelH, Nov 14 '16 at 08:49
Try [this](http://stackoverflow.com/questions/42519/how-do-you-rotate-a-two-dimensional-array), it may "inspire" you ! — BiLLiXx, Nov 14 '16 at 08:51
you can use 90 deg rotation with circle kernel and 45 deg rotation using square kernel see [Rotate a diagonal line in a 2D 3 x 3 grid - rotation matrix needed?](http://stackoverflow.com/a/40355825/2521214) non multiple of 90deg angle rotations using circle kernel is not 1:1 mapping meaning that some cells will be mapped to more then 1 cell causing big problems in matrices. Also you lost information out of bounds as rotated matrix has different bounding box size ... The best you can do is bilinear filtered rotation but that will change cell values which is in some cases unwanted — Spektre, Nov 14 '16 at 08:51
@Juvanis I've seen this type of manipulation used in [MUDs](https://en.wikipedia.org/wiki/MUD) when rotating a birdseye view of the world. — Rob, Nov 14 '16 at 08:51
@BiLLiXx The OP said in the question that they already know about the 90 degree solutions and they won't help. — Dawood ibn Kareem, Nov 14 '16 at 08:52
@Juvanis It comes close to what Rob said. I am creating a 2d topdown snapshot of each object in a 3d world. that 2d snapshot of the object is used for pathfinding. for each instance of the object the 2d snapshot with applied 'approximate' rotation added to the 2d walkgrid and marks it as unwalkable — user3488765, Nov 14 '16 at 08:57
@Spektre I love the GIF showing the problem with multiple 45° rotation ! Really nice answer — AxelH, Nov 14 '16 at 08:57
@AxelH yes that ASCII is nice example when the cell values must stay as is so no bi linear interpolation or subpixel precision can be used hence the problems. If this question is also the case is hard to know without Author's feedback — Spektre, Nov 14 '16 at 08:59
@Spektre loosing information is no big deal, as for each new call the 0° original will be used again. You link seems to be what I am looking for .) — user3488765, Nov 14 '16 at 09:00
@user3488765 and the cell values can interpolate or not ? output would be not just {0,1} but inbetween for non exact match positions — Spektre, Nov 14 '16 at 09:01
@Spektre yes they can, I use weighing in the pathfinding, 255 is absolutely unwalkable, 0 is absolutely walkable, everything inbetween is also an allowed value — user3488765, Nov 14 '16 at 09:10
@user3488765 if you want I can do a C++ example it is just an minor change to the `rot45cw()` example — Spektre, Nov 14 '16 at 09:14

score 1 · Answer 1 · answered Nov 14 '16 at 08:55

1

Imagine that your matrix is a 2D world, where its origin (0, 0) is the pixel in the middle. Then, for example, the coordinates of the point at the top-left corner would be (-2, 2). If you multiply this vector by a 2D rotation matrix, you will get the new coordinates in the rotated world. Here you can approximate as you like (round, floor, ciel, ...).

Here is the rotation matrix definition:

 | cos a      -sin a|
 | sin a      cos a |

where a is your rotation angle. Here is how you multiply:

https://wikimedia.org/api/rest_v1/media/math/render/svg/50622f9a4a7ba2961f5df5f7e0882983cf2f1d2f

In this image, (x, y) are the original coordinates (for example, (-2, 2) for the top-left corner pixel) and (x', y') are the new (approximated) coordinates.

answered Nov 14 '16 at 08:55

AhmadWabbi

2,253
1
20
35

I don't think this will work. If you use this method to rotate the square by 45 degrees, a sizeable portion of it ends up outside the target area. You also need to compress the corners inwards and stretch the edges outwards. – Dawood ibn Kareem Nov 14 '16 at 09:12
@DavidWallace Yeah, maybe a little bit of compressing and stretching will do the trick. This may be also solved using a simple `if` like `if (x > 2) x=2;` – AhmadWabbi Nov 14 '16 at 09:30
@AhmadWabbi I tried implementing your suggestion,.. where am I wrong? – user3488765 Nov 14 '16 at 09:40
@user3488765 Change `rotatedIdx[0] = (int)Math.Floor((originalIndexes[0] * (Math.Cos(angle) -Math.Sin(angle))));` into `rotatedIdx[0] = (int)Math.Floor(originalIndexes[0] * Math.Cos(angle) - originalIndexes[1] * Math.Sin(angle));` – AhmadWabbi Nov 14 '16 at 09:50
@user3488765 Also, change `(int)Math.Floor((originalIndexes[1] * (Math.Sin(angle) + Math.Cos(angle))));` into `rotatedIdx[1] = (int)Math.Floor(originalIndexes[0] * Math.Sin(angle) - originalIndexes[1] * Math.Cos(angle));` – AhmadWabbi Nov 14 '16 at 09:52
@user3488765 Also, before returning from `rotatedIndexes`, be sure that coordinates are between -2 and 2. For example, for `rotatedIdx[0]`, add `if (rotatedIdx[0] > 2) rotatedIds[0] = 2` and `if (rotatedIdx[0] < -2) rotatedIds[0] = -2` – AhmadWabbi Nov 14 '16 at 10:07

score 1 · Answer 2 · edited May 23 '17 at 12:24

It's already been implemented many times for image processing, in Photoshop, GIMP, ... and Imagemagick.

You could use a library (e.g. Python with numpy) to convert from a matrix to a bitmap image, ImageMagick to rotate it by x degrees and read the result from the rotated image back to a matrix. You would have to decide what to do with corners, they will get truncated if you want to rotate a n * n grid into a n * n grid.

It could be done in a few lines, you don't have to reinvent the wheel and you'd get gray values around the rotated point if it doesn't fall exactly in a cell.

Mini pictures :

Reading the results with Python :

import matplotlib.image as img
image = img.imread('matrix.png')

print image[:,:,0] # Only reads grayscale information.



# Original
[[ 0.  0.  1.  0.  0.]
 [ 0.  0.  1.  0.  0.]
 [ 1.  1.  1.  0.  0.]
 [ 0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.]]

# Rotated by 30°
[[ 0.07450981  0.          0.08235294  0.8509804   0.        ]
 [ 0.68627453  0.82745099  0.53725493  0.78039217  0.        ]
 [ 0.          0.50980395  0.97647059  0.22745098  0.        ]
 [ 0.          0.          0.05882353  0.          0.        ]
 [ 0.          0.          0.          0.          0.        ]]

For a Java solution, AffineTransform could help you. Here's an example.

this is exactly what I am looking for! But I'd need code in Java or C#. — user3488765, Nov 14 '16 at 09:51
https://docs.oracle.com/javase/7/docs/api/java/awt/geom/AffineTransform.html could help you with Java. Here's an example : http://stackoverflow.com/questions/8639567/java-rotating-images — Eric Duminil, Nov 14 '16 at 09:58

score 1 · Accepted Answer · answered Nov 14 '16 at 09:57

Ok here it is as promised. First C++ code:

//---------------------------------------------------------------------------
#include <math.h>
//---------------------------------------------------------------------------
const int xs=7; // matrix size
const int ys=7;
const int x0=3; // rotation center cell
const int y0=3;
const float deg=M_PI/180.0;
int A[xs][ys]=
    {
    {0,0,0,9,0,0,0},
    {0,0,0,9,0,0,0},
    {0,0,0,9,0,0,0},
    {9,9,9,9,0,0,0},
    {0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0},
    };
int B[xs][ys];
//---------------------------------------------------------------------------
void rotcw(int x0,int y0,float ang) // rotate A -> B by angle ang around (x0,y0) CW if ang>0
    {
    int x,y,ix0,iy0,ix1,iy1,q;
    float xx,yy,fx,fy,c,s;
    // circle kernel
    c=cos(-ang); s=sin(-ang);
    // rotate
    for (y=0;y<ys;y++)
     for (x=0;x<xs;x++)
        {
        // offset so (0,0) is center of rotation
        xx=x-x0;
        yy=y-y0;
        // rotate (fx,fy) by ang
        fx=float((xx*c)-(yy*s));
        fy=float((xx*s)+(yy*c));
        // offset back and convert to ints and weights
        fx+=x0; ix0=floor(fx); fx-=ix0; ix1=ix0+1; if (ix1>=xs) ix1=ix0;
        fy+=y0; iy0=floor(fy); fy-=iy0; iy1=iy0+1; if (iy1>=ys) iy1=iy0;
        // bilinear interpolation A[ix0+fx][iy0+fy] -> B[x][y]
        if ((ix0>=0)&&(ix0<xs)&&(iy0>=0)&&(iy0<ys))
            {
            xx=float(A[ix0][iy0])+(float(A[ix1][iy0]-A[ix0][iy0])*fx);
            yy=float(A[ix0][iy0])+(float(A[ix1][iy0]-A[ix0][iy0])*fx);
            xx=xx+((yy-xx)*fy); q=xx;
            } else q=0;
        B[x][y]=q;
        }
    }
//---------------------------------------------------------------------------

Here 7x7 preview 15 deg steps:

It may be need a bit tweaking of the center by half of cell or something (the center is bleeding too much to my liking)

Matrix A is source and B is target ...

You can also add tresholding ... like:

if (q>=5) q=9; else q=0;

thanks alot, tried it in c# and it worked. The conversion is in my OP — user3488765, Nov 14 '16 at 10:31
@user3488765 you can use the `deg` constant ... `rotAngle += 90.0*deg;` That is its purpose ... — Spektre, Nov 14 '16 at 11:19

How can I rotate a 2d array by LESS than 90°, to the best approximation?

3 Answers3

Linked