Code:

#include <iostream>
#include <cstring>
#include <cmath>
#include <assert.h>
#define PIE 3.1415926535897
#define ALMOST_ZERO (1e-10)
using namespace::std;
#define ELEM_AT(a,x,y,w) (a[y*w+x])
// Find nearest integer
int nint(double x)
{
return int( x >= 0 ? x+0.5 : x-0.5);
}
int newWidth;
int newHeight;
// Find center index of array given the array dimension
int centerIndex(int dimension)
{
return nint(double(dimension-1)/2);
}
void dump(const unsigned int* array, int width, int height)
{
for(int y = 0; y < height; ++y)
{
for(int x = 0; x < width; ++x)
{
int elem = ELEM_AT(array, x, y, width);
cout << char(elem == 0 ? '*' : elem);
}
cout << endl;
}
cout << endl;
}
struct Location
{
Location(int X, int Y) { x = X; y = Y; }
int x;
int y;
};
ostream& operator<<(ostream& out, const Location& loc)
{
out << "(" <<
loc.x << ',' << loc.y
<< ")";
return out;
}
void rotate(const unsigned int* array, int height, int width, int angle)
{
double rads = ( angle * PIE * 2) / 360;
double sinAngle= sin(rads);
if (fabs(sinAngle) < ALMOST_ZERO) sinAngle = 0;
double cosAngle = cos(rads);
if (fabs(cosAngle) < ALMOST_ZERO) cosAngle = 0;
cout << "------------------------------------------\n";
cout << "Input:\n";
dump(array, width, height);
// Array will be rotated around this point
int centerX = centerIndex(width);
int centerY = centerIndex(height);
// These will be used to determine dimensions of the new rotated array
int lowestX = INT_MAX;
int lowestY = INT_MAX;
int highestX = INT_MIN;
int highestY = INT_MIN;
// Phase 1: Calculate new locations for each element of array
Location* newLocations = (Location*)calloc(width * height, sizeof(Location));
for(int y = 0; y < height; ++y)
{
for(int x = 0; x < width; ++x)
{
int dx = (x - centerX);
int dy = (y - centerY);
int elem = char(ELEM_AT(array, x, y, width));
if (elem != 0)
{
double newX;
double newY;
newX = centerX - dy*sinAngle + dx*cosAngle;
newY = centerY + dy*cosAngle + dx*sinAngle;
/* Account for the fact that cells that are not horizontally or vertically
adjacent are farther appart in distance
For example
AB
CD
A,B and A,C are one cell appart, but the distance A,D is 1 * square root 2
or 1 / sin of the angle
*/
if (sinAngle != 0)
{
newX /= fabs(sinAngle);
newY /= fabs(sinAngle);
}
Location loc(nint(newX), nint(newY));
if (loc.x < lowestX) lowestX = loc.x;
if (loc.y < lowestY) lowestY = loc.y;
ELEM_AT(newLocations, x, y, width) = loc;
}
}
}
cout << "New Locations:" << endl;
// Phase 2:
// Subtract lowestX and lowestY elements from each X,Y point in
// newLocation so that all locations are positive and can be used as indicies into the
// rotated array
// Determine highestX and highestY to assist in calculating newWidth and newHeight
for(int y = 0; y < height; ++y)
{
for(int x = 0; x < width; ++x)
{
cout << ELEM_AT(newLocations, x, y, width);
if (lowestX < 0) ELEM_AT(newLocations, x, y, width).x -= lowestX;
if (lowestY < 0) ELEM_AT(newLocations, x, y, width).y -= lowestY;
if (ELEM_AT(newLocations, x, y, width).x > highestX) highestX = ELEM_AT(newLocations, x, y, width).x;
if (ELEM_AT(newLocations, x, y, width).y > highestY) highestY = ELEM_AT(newLocations, x, y, width).y;
}
cout << endl;
}
cout << "Lowest X " << lowestX << endl;
cout << "Lowest Y " << lowestY << endl;
cout << "Highest X " << highestX << endl;
cout << "Highest Y " << highestY << endl;
// For the sake of appearance, do not make the new arrray dimensions smaller that the original
newWidth = max(highestX+1, width);
newHeight = max(highestY+1, height);
cout << "\nOutput: " << angle << " degrees: " << width << "x" << height << " -> " << newWidth << "x" << newHeight << endl;
// Phase 3: Create the new array and populate it
unsigned int* newArray = (unsigned int *) calloc(newWidth * newHeight, sizeof(*array));
for(int y = 0; y < height; ++y)
{
for(int x = 0; x < width; ++x)
{
int elem = char(ELEM_AT(array, x, y, width));
if (elem != 0)
{
int newX = ELEM_AT(newLocations, x, y, width).x;
int newY = ELEM_AT(newLocations, x, y, width).y;
assert(newX >= 0);
assert(newX < newWidth);
assert(newY >= 0);
assert(newY < newHeight);
ELEM_AT(newArray, newX, newY, newWidth) = elem;
}
}
}
dump(newArray, newWidth, newHeight);
// Free the work area
free(newLocations);
// Free the newArray if it is not being returned
free(newArray);
return;
}
int main(void)
{
unsigned int degenerateCase[1][1] =
{
{'X'}
};
unsigned int smallH[1][2] =
{
{'X', 'Y'}
};
unsigned int smallV[2][1] =
{
{'X'},
{'Y'}
};
unsigned int smallSq[2][2] =
{
{'a', 'b'},
{'1', '2'}
};
unsigned int rectangularH[3][7] =
{
{'a', 'b', 'c', 'd', 'e', 'f' ,'g'},
{'1', '2', '3', '4', '5', '6', '7'},
{'H', 'I', 'J', 'K', 'L', 'M', 'N'}
};
unsigned int rectangularV[7][3] =
{
{'a', '1', 'A'},
{'b', '2', 'B'},
{'c', '3', 'C'},
{'d', '4', 'D'},
{'e', '5', 'E'},
{'f', '6', 'F'},
{'g', '7', 'G'}
};
unsigned int squareEven[6][6] =
{
{0,0,'a','1',0,0},
{0,0,'b','2',0,0},
{0,0,'c','3',0,0},
{0,0,'d','4',0,0},
{0,0,'e','5',0,0},
{0,0,'f','6',0,0}
};
//rotate((unsigned int*)°enerateCase[0][0], 1, 1, 0);
//rotate((unsigned int*)°enerateCase[0][0], 1, 1, 45);
//rotate((unsigned int*)°enerateCase[0][0], 1, 1, 90);
//rotate((unsigned int*)°enerateCase[0][0], 1, 1, 180);
//rotate((unsigned int*)&smallH[0][0], 1, 2, 0);
//rotate((unsigned int*)&smallH[0][0], 1, 2, 45);
//rotate((unsigned int*)&smallH[0][0], 1, 2, 90);
//rotate((unsigned int*)&smallH[0][0], 1, 2, 180);
//rotate((unsigned int*)&smallV[0][0], 2, 1, 0);
//rotate((unsigned int*)&smallV[0][0], 2, 1, 45);
//rotate((unsigned int*)&smallV[0][0], 2, 1, 90);
//rotate((unsigned int*)&smallV[0][0], 2, 1, 180);
//rotate((unsigned int*)&smallSq[0][0], 2, 2, 0);
//rotate((unsigned int*)&smallSq[0][0], 2, 2, 45);
//rotate((unsigned int*)&smallSq[0][0], 2, 2, 90);
//rotate((unsigned int*)&smallSq[0][0], 2, 2, 180);
//rotate((unsigned int*)&rectangularH[0][0], 3, 7, 0);
rotate((unsigned int*)&rectangularH[0][0], 3, 7, 45);
//rotate((unsigned int*)&rectangularH[0][0], 3, 7, 90);
//rotate((unsigned int*)&rectangularH[0][0], 3, 7, 180);
//rotate((unsigned int*)&rectangularV[0][0], 7, 3, 0);
rotate((unsigned int*)&rectangularV[0][0], 7, 3, 45);
//rotate((unsigned int*)&rectangularV[0][0], 7, 3, 90);
//rotate((unsigned int*)&rectangularV[0][0], 7, 3, 180);
//rotate((unsigned int*)&squareEven[0][0], 6, 6, 0);
//rotate((unsigned int*)&squareEven[0][0], 6, 6, 45);
//rotate((unsigned int*)&squareEven[0][0], 6, 6, 90);
//rotate((unsigned int*)&squareEven[0][0], 6, 6, 180);
//rotate((unsigned int*)&squareEven[0][0], 6, 6, 0);
//rotate((unsigned int*)&squareEven[0][0], 6, 6, 45);
//rotate((unsigned int*)&squareEven[0][0], 6, 6, 90);
//rotate((unsigned int*)&squareEven[0][0], 6, 6, 180);
//for(int angle = 0; angle < 90; angle += 5) rotate((unsigned int*)&rectangular[0][0], 3, 7, angle);
return 0;
}

When the array is rotated, the resulting array often has empty rows or columns. Part of that is intentional, but sometimes there is more than necessary. I'll leave it up to you to trim the result if you like.