How to rotate a bidimensional byte array?

Question

I have the need to rotate the data in a bidimensional square byte matrix in any degree (0~359)

My matrix is composed by a 16x16 byte square like this:

[00][00][00][00][00][00][00][00][00][00][00][00][00][00][00][00]
[00][00][00][00][00][00][00][00][00][00][00][00][00][00][00][00]
[00][00][00][00][00][00][00][00][00][00][00][00][00][00][00][00]
[00][00][00][00][00][00][00][00][00][00][00][00][00][00][00][00]
[00][00][00][00][00][00][00][00][00][00][00][00][00][00][00][00]
[00][00][00][00][00][00][7F][7F][7F][7F][7F][7F][7F][7F][00][00]
[00][00][00][00][00][00][7F][7F][7F][7F][7F][7F][7F][7F][00][00]
[00][00][00][00][00][00][7F][7F][7F][7F][7F][7F][7F][7F][00][00]
[00][00][00][00][00][00][7F][7F][7F][7F][7F][7F][7F][7F][00][00]
[00][00][00][00][00][00][7F][7F][7F][7F][7F][7F][7F][7F][00][00]
[00][00][00][00][00][00][00][00][7F][7F][00][00][00][00][00][00]
[00][00][00][00][00][00][00][00][00][00][00][00][00][00][00][00]
[00][00][00][00][00][00][00][00][00][00][00][00][00][00][00][00]
[00][00][00][00][00][00][00][00][00][00][00][00][00][00][00][00]
[00][00][00][00][00][00][00][00][00][00][00][00][00][00][00][00]
[00][00][00][00][00][00][00][00][00][00][00][00][00][00][00][00]

This matrix represents a collision map of an item in a game. The numbers in the matrix represents the height of each position in the game world to be used to determine collision with other objects in the game.

I need to be able to rotate this collision map (the matrix data), as the object in the game can be rotated.

Does anyone have any idea how I could accomplish this?

Thank you very much!

Well, when you rotate it 45 degrees, it won't be 16x16 anymore unless you cut off the edges. Is that okay? Also, might it not be faster to rotate the objects instead of the map? — Norman, Feb 19 '16 at 16:51
Hello Norman, it's completely okay to cut off the edges. And for the other question: the problem is that the objects which have these collision maps can be rotated, but once the object is rotated I have to update the collision map according the rotation applied to the object. — andresantacruz, Feb 19 '16 at 17:19
Rotation by multiples of 90 degrees is trivial; for every other angle interpolation comes into play. Say for some angle you calculate that the indices into your original matrix are 3.5 and 14.2. What kind of interpolation do you require then? Is nearest-neighbor good enough, or is interpolation acceptable at all? — Norman, Feb 19 '16 at 18:38

score 3 · Accepted Answer · answered Feb 20 '16 at 18:04

You need a function f(x,y) that rotates the coordinates x,y in your collision map by an angle theta. With it, you can either

calculate where an element of the collision map would move when rotated by theta (e.g. (0,0) would move to (15,0) when rotated by 90 degrees clockwise), or
you can calculate which element would have been moved to a certain position by a rotation of theta degrees. In this case, you'll flip the sign of theta to reverse the direction.

To create a rotated map, you'll do #2. Create a second map of same size, then loop over all of its elements and replace each with the corresponding element from the unrotated map. You get the coordinates of a corresponding element by feeding the coordinates of an element into the function f(x,y).

Now for f(x,y): this function can be built by combining 3 affine transformations matrices that will rotate your coordinates about the center of the collision map.
I should explain this at a later time :-)

These equations give you the coordinates (x',y') of the element corresponding to the coordinates (x,y):

x' =  c * x + s * y - a * (1 - c - s)
y' = -s * x + c * y - a * (1 - c + s)

where

c = cos(-theta)
s = sin(-theta)
a = +0.5 - 0.5 * N
N = side length of your square collision map (i.e. 16)
theta = angle of clockwise rotation
        (but effectively counter-clockwise for the way that you
         usually visualize arrays, i.e. y-axis pointing downwards)

So f(x,y) is the function returning x' and y'.

After these floating-point calculations, you'll need to correctly round the result coordinates (x',y') to the nearest integer values. When those rounded coordinates then lie outside of the array, then no corresponding element exists and you should use 0 as the value for that element (or whatever value represents level terrain or no collision).

Rounding the coordinates to integers gives nearest-neighbor interpolation.
Another option would be bilinear interpolation, where you'd average the values of the 4 elements closest to the fractional coordinates. (Example: for 2.4, 5.7, you'd average the values of the elements at 2,5, 2,6, 3,5, and 3,6.)

You may always ask for clarification :-) In this case, I could not infer much about your background. As you added a "math" tag but no programming language tag, I tried to give an explanation rather than a code snippet. (Though the code snippet might have been faster both to write and to understand ...) — Norman, Feb 25 '16 at 00:33
Yes, I should put some tag about programming, but I used your alghoritm easily. I took some time learning about interpolation and stuff, things I didn't know. — andresantacruz, Feb 25 '16 at 01:05

Matheus Santos · Answer 2 · 2022-03-06T09:19:52.483

I was so amazed by Norman's answer that I had to share my badly written Python code here just to show how the calculation works well!

from math import sin,cos,floor
import os,time

height = 16
width = 16
angle = 0
# Because python is weird sometimes - https://stackoverflow.com/questions/2397141/how-to-initialize-a-two-dimensional-array-in-python
tmp= [ [0]*16 for i in range(16)]

#My bitmap is actually a sprite pattern
bitmap=[
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
    [0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0],
    [0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0],
    [0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0],
    [0,0,1,0,0,0,0,1,1,0,0,0,0,1,0,0],
    [0,0,1,0,0,0,1,1,1,1,0,0,0,1,0,0],
    [0,0,1,0,0,1,1,0,0,1,1,0,0,1,0,0],
    [0,0,1,0,0,1,0,0,0,0,1,0,0,1,0,0],
    [0,0,1,0,0,0,0,1,1,0,0,0,0,1,0,0],
    [0,0,1,0,0,0,0,1,1,0,0,0,0,1,0,0],
    [0,0,1,0,0,0,0,1,1,0,0,0,0,1,0,0],
    [0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0],
    [0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    ]

while(angle < 6.2):
    os.system('clear') #replace clear with cls if OS == Windows
    for x in range (0,height):
        for y in range(0,width):
            rx =  cos(-angle) * x + sin(-angle) * y - (+0.5 - (0.5 * height)) * ( 1 - cos(-angle) - sin(-angle))
            ry = -sin(-angle) * x + cos(-angle) * y - (+0.5 - (0.5 * width))  * ( 1 - cos(-angle) + sin(-angle))
            if ( round(rx) >= 0 and round(rx) < width and round(ry) >= 0 and round(ry) < height):
                tmp[x][y]=bitmap[round(rx)][round(ry)]
            else:
                tmp[x][y]=0
        print("\r\n",end='')

    for x in range (0,height):
        for y in range(0,width):
            if (tmp[x][y]) == 0:
                print (".",end='')
            else:
                print ("1",end='')
        print("\r\n", end='')

    print(angle)
    angle = angle + 0.1
    time.sleep(.1)

How to rotate a bidimensional byte array?

2 Answers2