Поворот картинки (транспонирование матрицы), Как сделать через перестановки? Опции

[RHnd]

Не совсем уверен, что правильно выбрал подфорум, но, надеюсь, мне помогут.
Задача ставиться так - в памяти лежит картинка NxM, ее нужно повернуть против часовой стрелки на 90 градусов. Так как картинка большая, а памяти мало, то просто переписать ее в новый блок памяти нельзя. Мне кажетя, что должен быть какой-то алгоритм перестановки элементов картинки, решающий задачу, но найтк его как-то не удается.

Пример:
По сути, задача сводится к транспонированию матрицы. Есть матрица 4x3, из нее получается 3x4:

Код

1 2 3                       3 6 9 C
4 5 6           =>          2 5 8 B
7 8 9                       1 4 7 A
A B C

В линейном виде (как в памяти лежит):
Было: Picture[12] = 1 2 3 4 5 6 7 8 9 A B C
Стало: NewPictute[12] = 3 6 9 С 2 5 8 B 1 4 7 A

А вот каким алгоритмом можно переставить элементы Picture так чтобы получился NewPicture для произвольных N и M, я не знаю. Подскажите, пожалуйста!

[SasaTheProgramme...]

Вот какое-то решение из ФИДО (извините ребята, я сейчас анализировать/проверять не могу. И вообще ничего не могу).
=======
Alex Kocharin wrote:
> Комбинация транспонирования и отражения.
>
> Транспонирование:
> (x,y) -> (y,x)
> x*N+y -> y*M+x
>
> Отражение:
> (x,y) -> (x,M-y-1)
> x*M+y -> x*M+M-y-1
>
> Т.е.
> x*N+y -> y*M+M-x-1
>
> Отбратно: транспонирование:
> (x,y) -> (y,x)
> x*N+y -> y*M+x
>
> Отражение:
> (x,y) -> (N-x-1,y)
> x*N+y -> (M-x-1)*N+y
>
> Т.е.
> x*N+y -> (M-y-1)*N+x
>
> Программа (не оптимизированная):
>
> for(int i=0; i<M*N; i++) {
> int x1 = i/N, y1 = i-x1*N;
> int prev = (M-y1-1)*N+x1;
> if (prev < i) {
> int ires = y1*M+M-x1-1;
> int t = picture[ires];
> picture[ires] = picture[i];
> picture[i] = t;
> }
> }
>
> Сдаём заказчику:
>
> int i;i^=i;for(;i<M*N;){int x1=i/N,y1=i-x1*N,p=M*N-y1*N-N+x1;if(p<i){int
> r=y1*M+M-x1-1,t=p[r];p[r]=p[i];p[i++]=t;}}
>
> Проверяй. ;-)))
>
> Возможно, я где-то ошибся - там N вместо M или единичка где лишняя... По
> крайней мере, идея imho верная.
>
>
=======