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

[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...]

Не совсем уверен, что правильно выбрал подфорум, но, надеюсь, мне помогут.
Задача ставиться так - в памяти лежит картинка 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, я не знаю. Подскажите, пожалуйста!

Подозреваю, что просто не получится. Допустим, мы "подняли" некий элемент, вычислили его новый адрес, "подняли" эелемент по новому адресу, положили на его место первый "поднятый". Теперь нужно "пристроить" "висящий" элемент - вычисляем его новый адрес и т.д. Но тут может получиься кольцо, т.е. не перебрав всей матрицы мы вернёмся к адресу первого "поднятого" элемента. Эту ситуацию нужно уметь детектировать и выбирать новый "первый" элемент. Насколько эта ситуация реальна мне сказать трудно, теория чисел не является моим сильным местом. Я бы посоветовал обратиться в fido7.ru.math - там точно с этим справятся. Но если это действительно может случится, то алгоритм может получиться жутко прожорливым как по памяти, так и по времени.
А нельзя ли эту матрицу использовать как она есть? Т.е. при обращении к ней переставлять индексы. Или, если она представлена одномерным массивом - руками вычислять смещение i*M+j вместо j*N+i ?

[Doka]

А нельзя ли эту матрицу использовать как она есть? Т.е. при обращении к ней переставлять индексы. Или, если она представлена одномерным массивом - руками вычислять смещение i*M+j вместо j*N+i ?

кстати, да.. забавно, что этого никто не предложил)
вполне рабочее решение если массив потом используется для вывода (или для обработки не требующей строгой ориентации (верт/гориз))