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

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

В линейном виде (как в памяти лежит):
Было: 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, я не знаю. Подскажите, пожалуйста!

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

Попробуйте оперировать двумерными массивами (для памяти всё равно - а программить легче).

тогда задача хорошо параметризуется:
два вложенных цикла с переписыванием массивов.
внешний - по столбцам - с последнего по первый (из столбцов в строки)
внутренний - по элементам столбца (строкам) - с первого по последний




upd: прошу прощения - не увидел про ограничение на память(

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

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

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

Да, точно.


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


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


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

1. В дсп камнях часто присутствует двумерное дма.
2. Двумерный массив отличается от одномерного только расчетом индекса т.е. можеш в начале засыпать в одномерный массив а потом по этому же начальному адресу обьявить двумерный массив нужной размерности (нужно аккуратно делать поскольку если неправильно то можно вылететь в чужую память), второй вариант самому считать индекс для массива при считывании.

И чем это поможет? Мне-то нужно в рамках имеющейся памяти упорядочить масив так, чтоб он представлял собой повернутую картинку.

Ничего специального не нужно, только зарегистрироваться для того чтобы постить. Читать можно даже через гугль :-). Видел в некоторых письмах "отправлено через форум mail.ru", а сам предпочитаю доступаться через ddt.demos.su . Аутлук или тандербирд...

P.S. Отфорвардил туда исходный вопрос, можно гуглить ветку по сабжу "Вопрос с форума".

Алгоритм циклической перестановки для поворота картинки достаточно прост. В Ваших терминах:

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

берём первый элемент исходного массива «1», он попадает в 9-ю позицию, переставляем, предварительно подняв 9-ку, она переходит в 3-ю позицию и т.д. Для наглядности удобно карандашом рисовать стрелки перестановок – т.е. от верхней «1» кривая стрелка к нижней «1». От нижней «1» вертикально вверх стрелка попадает в девятку и т.д.
В пределах массива образуется группа циклической перестановки элементов. Т.к. элементы исходного и конечного массивов соответствуют 1:1, то никаких пересечений быть не может. Проблема в другом.

Ниже текст примитивной программки выполняющей вышеописанные действия (программа не правильная :-)).

#include <stdio.h>
#include <math.h>

#define MaxA 4
#define MaxB 3
#define MaxC MaxB
#define MaxD MaxA

//--------------------------------

int main(void) {
int a,b,c,d, x,pp,tmp1,tmp2;

union {
int In[MaxA*MaxB];
int Out[MaxC*MaxD];
} Matrix;



x = 0;
for(b=0;b<MaxB;b++)
for(a=0;a<MaxA;a++)
Matrix.In[a + b*MaxA] = x++;


for(b=0;b<MaxB;b++)
{ printf("\n");
for(a=0;a<MaxA;a++)
printf(" %5d ",Matrix.In[a + b*MaxA]);
}

printf("\n");printf("\n");printf("\n");


//#################################
x=0;
a=0; b=0;
tmp1 = Matrix.In[0];

for(;;)
{ if (x++ > MaxA * MaxB) break;

c=b; d=MaxD-1-a;
tmp2 = Matrix.Out[c + d*MaxC];
Matrix.Out[c + d*MaxC] = tmp1;

tmp1 = tmp2;

pp= c + d*MaxC;
b= (int) pp/MaxA;
a= (int) pp - (b*MaxA);

if ((a==0)&&(b==0)) break;
}
//#################################


for(d=0;d<MaxD;d++)
{ printf("\n");
for(c=0;c<MaxC;c++ )
printf(" %5d ",Matrix.In[c + d*MaxC]);
}

return 0;
}

Основная проблема (как и неправильность программы) заключается в том, что группа циклических перестановок не обязательно одна, полностью охватывающая весь массив. Например, для массива 2х3 цепочка одна, а уже для 3х4 циклическая перестановка захватывает только часть элементов. Т.е. для произвольного массива может быть несколько цепочек перестановки – вот в нахождение этих цепочек и есть большая засада. Выполнив одну цепь перестановок тяжело сказать какие элементы ещё остались не переставленными.

Можно предложить несколько путей решения, начну с наихудшего (как для меня):

1. Аналитическое решение. Как для меня – совершенно не интересная задача :-)

2. Написать программку моделирования и прогнать все допустимые размеры входных массивов. Возможно там что-то можно будет увидеть и составить типа таблички или вывести формулку.

3. Выделить битовый массив, с размерами исходного, и в нём отмечать переставленные элементы. После окончания цепи перестановок (окончание цепи – попадаем на позицию элемента, с которого начинали) – в случае недостающего количества перестановок – по массиву находим любой незадействованный элемент и начинаем новую цепь. Дополнительные расходы памяти, чего Вы страшно не хотите.

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

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

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

Не знаю на сколько еще актуально...

Посмотрите книгу "Быстрые алгоритмы в цифровой обработке изображений. Преобразования и медианные фильтры" Под ред. Т.С. Хуанга. Там целый раздел посвящен вопросу транспонирования матриц, причем большое внимание уделяется работе с запоминающими устройствами с последовательным доступом (читай: двумерный массив представлен одномерным). Описаны быстрые (!) алгоритмы, приведены книги где еще можно посмотреть (тот же Кнут упоминается). Почитайте. В свое время книгу эту качал на dsp-book.narod.ru. Ищите, если не найдете, то выложу куда скажете....

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

Считайте, что у вас матрица в одномерном массиве (так и есть - память линейная ). Транспонирование матрицы - это перестановка элементов линейного массива в этой линейной памяти. Любая перестановка элементов упорядоченного множества распадается на набор циклических перестановок. Для квадратной матрицы это - попарные перестановки, для приямоугольной - более длинные циклы. Если элемент матрицы размера 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 и так далее, пока цикл не завершается. Можно бойтись вообще без дополнительной памяти - на каждом шаге переставлять элементы с началом цикла.

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

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

Из уравнений

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

следует, что

b = N*a mod N*M-1

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

Вот какое-то решение из ФИДО (извините ребята, я сейчас анализировать/проверять не могу. И вообще ничего не могу).
=======
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 верная.
>
>
=======