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

[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, я не знаю. Подскажите, пожалуйста!

[blackfin]

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

Скорее, к транспонированию с последующим зеркальным отражением относительно
горизональной линии проходящей через середину матрицы (M/2).
Можно выполнить поворот "на месте", если зарезервировать память под
квадратную матрицу, т.е. 4х4, но лучше, сразу заполнять память в нужном порядке.

Сообщение отредактировал blackfin - May 18 2007, 18:04

[RHnd]

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

Да, точно.

Можно выполнить поворот "на месте", если зарезервировать память под
квадратную матрицу, т.е. 4х4, но лучше, сразу заполнять память в нужном порядке.

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

Квадратную матрицу делать нельзя - массив может быть как 1000x1000, так и 10000x1. А памяти мало.
Так же не получится изначально записывать в нужном порядке - в момент начала прихода картинки мы еще ничего не знаем о ее размерах. Фактически, можно сказать, что нам постфактум сообщаются адрес начала, ширина и высота. На счет вычисления адресса руками тоже не пройдет - на выходе мы так же должны предоставить адрес начала, ширину и высоту (новые), а там дальше внешняя прога начнет эти данные гнать наружу.

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

Нет, так не получится. Действительно, как отметил SasaTheProgrammer, зацикливание произойдет. Причем, произойдет обязательно.

Я бы посоветовал обратиться в fido7.ru.math - там точно с этим справятся.

А не подскажете, как туда обратиться? Когда-то давно и сам был фидошником, но с тех пор, как интернет прочно вошел в мою жизнь, отстал от положения дел. Там, вроде, надо какой-то специальный софт ставить или что-то такое?

Сообщение отредактировал RHnd - May 18 2007, 20:35