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

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

Вот придумался алгоритм - очень не быстрый и требующий немножко памяти (всё-таки). Требуется буфер на одну строку. Допустим, исходный массив был M по горизонтали и N по вертикали. Нужен буфер на N позиций. Проходим по массиву. выклёвывая в буфер каждый M-тый элемент начиная с нулевого, т.е. перемещаем в буфер первый столбец. Теперь уплотняем массив (ой сколько пересылок!!! M вызовов memcpy!) с учётом скопированных элементов. Получившееся рассматриваем как массив (M-1)*N и свободный (!) хвост длины N. Переписываем буфер в хвост и повторяем всё сначала...

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

[RHnd]

Вот придумался алгоритм - очень не быстрый и требующий немножко памяти (всё-таки). Требуется буфер на одну строку. Допустим, исходный массив был M по горизонтали и N по вертикали. Нужен буфер на N позиций. Проходим по массиву. выклёвывая в буфер каждый M-тый элемент начиная с нулевого, т.е. перемещаем в буфер первый столбец. Теперь уплотняем массив (ой сколько пересылок!!! M вызовов memcpy!) с учётом скопированных элементов. Получившееся рассматриваем как массив (M-1)*N и свободный (!) хвост длины N. Переписываем буфер в хвост и повторяем всё сначала...

учитывая, что время нам не критично, то это действительно пока-что лучший алгоритм.
PS: Сегодня согласовывал память. Возможно, выделится место под дополнительный кадр.

[Oldring]

учитывая, что время нам не критично, то это действительно пока-что лучший алгоритм.
PS: Сегодня согласовывал память. Возможно, выделится место под дополнительный кадр.

Все тривиально. Особенно, если память с произвольным доступом, нет жестких требований по времени работы, но есть жесткие олграничения на используемую дополнительную память.

Считайте, что у вас матрица в одномерном массиве (так и есть - память линейная ). Транспонирование матрицы - это перестановка элементов линейного массива в этой линейной памяти. Любая перестановка элементов упорядоченного множества распадается на набор циклических перестановок. Для квадратной матрицы это - попарные перестановки, для приямоугольной - более длинные циклы. Если элемент матрицы размера MxN имел индекс (i,j), его смещение в исходном массиве было M*i+j, и он переходит в элемент N*j+i. Пусть в этой ячейке располагается элемент (k,m). Имеем уравнение:

M*k+m = N*j+i

откуда

k = floor( (N*j+i) / M )
m = mod( N*j+i, M )

Далее мы переносим уже этот элемент в ячейку с индексом N*k+m и так далее, пока цикл не завершается. Можно бойтись вообще без дополнительной памяти - на каждом шаге переставлять элементы с началом цикла.

Ну и осталось правильно вычислить набор начальных элементов циклов и немного соптимизировать процесс вычисления индексов

[Oldring]

Ну и осталось правильно вычислить набор начальных элементов циклов и немного соптимизировать процесс вычисления индексов

По поводу оптимизации вычисления индексов.

Из уравнений

a = M*i+j
b = N*j+i

следует, что

b = N*a mod N*M-1

Если N*M является степенью двойки, или степенью двойки + 1 - то на поцессоре с быстрым умножением итерация становится тривиальной.