Войти
ПрограммированиеФорумОбщее

In-place transpose 2D bitmap

Страницы: 1 2 Следующая »
#0
16:18, 16 авг 2022

Есть некий битмап в буфере. Надо его транспонировать. Если он квадратный то все просто, но есть ли способы сделать это на NxM без доп аллокаций?

#1
18:51, 16 авг 2022

Андрей5000
Допустим, у нас такая матрица:

| 1 | 2 | 3 |
------------
| 4 | 5 | 6 |
------------
| 7 | 8 | 9 |
------------
| A | B | C |
------------

Для получения квадратной, дополняем матрицу столбцом:

| 1 | 2 | 3 | 0 |
----------------
| 4 | 5 | 6 | 0 |
----------------
| 7 | 8 | 9 | 0 |
----------------
| A | B | C | 1 |
----------------

Т.о. транспонированный вариант получится таким:

| 1 | 4 | 7 | A |
----------------
| 2 | 5 | 8 | B |
----------------
| 3 | 6 | 9 | C |
----------------
| 0 | 0 | 0 | 1 |
----------------

Если теперь вернуться к старой размерности, получим:

| 1 | 4 | 7 |
------------
| 2 | 5 | 8 |
------------
| 3 | 6 | 9 |
------------
| 0 | 0 | 0 |
#2
19:17, 16 авг 2022

nes
Без аллокаций надо же. А в твоем для случая 10х1000 надо выделить еще память под 990х1000 элементов

#3
19:27, 16 авг 2022

Андрей5000
> но есть ли способы сделать это на NxM без доп аллокаций?
Есть конечно. Смотри, в квадратном случае транспонирование - это swap двух элементов, при этом свапнутые уже трогать нельзя. Чтобы скипнуть свапнутые пиксели в квадратном случае ты например делаешь цикл по пикселям выше диагонали.
Но скипнуть свапнутые пиксели ведь можно по другому. Например можно пройти весь массив, и свапать только те пиксели, у которых старый индекс меньше (или больше) нового.

struct Img {
  int w;
  int h;
  pixel* data;
};

ivec2 IndexToCoord(int idx, int w) {
  return ivec2(idx % w, idx / w);
}

int CoordToIndex(ivec2 coord, int w) {
  return coord.y * w + coord.x;
}

void Transpose(Img& img) {
  for (int i = 0; i < img.w*img.h; i++) {
    ivec2 old_coord = IndexToCoord(i, img.w);
    int new_idx = CoordToIndex(ivec2(old_coord.y, old_coord.x), img.h);
    if (i < new_idx) { //пропускаем уже свапнутые пиксели
      Swap(data[i], data[new_idx]);
    }
  }
  int new_w = img.h;
  int new_h = img.w;
  img.w = new_w;
  img.h = new_h;
}
#4
19:29, 16 авг 2022

Андрей5000
>выделить еще память под 990х1000 элементов
Зачем ее выделять?

#5
19:39, 16 авг 2022

MrShoor
>//пропускаем уже свапнутые пиксели
Сдается мне, что без этого условия будет шустрее.

#6
19:41, 16 авг 2022

nes
> Сдается мне, что без этого условия будет шустрее.
Может и шустрее, но не правильно.

#7
9:33, 17 авг 2022

https://en.wikipedia.org/wiki/In-place_matrix_transposition

#8
9:47, 17 авг 2022

Suslik

Ага, я тоже вчера на простеньких массивах увидел что возможны перестановочные циклы, причём разрозненные и дальше думать стало лень.

#9
11:05, 17 авг 2022

MrShoor
что то не фурычит такой простой подход: https://ideone.com/b7xY6u

nes
> Зачем ее выделять?
А как?

#10
11:55, 17 авг 2022

Андрей5000
>А как?
По циклу свопать элементы, например как в примере мистера Шурика.

#11
11:56, 17 авг 2022

Ща накидаю кодяру.

#12
12:15, 17 авг 2022

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

#13
13:43, 17 авг 2022

Андрей5000
> Если он квадратный то все просто, но есть ли способы сделать это на NxM без доп
> аллокаций?
есть способ сделать за 1.

+ Показать
#14
14:05, 17 авг 2022

Вот, оказалось и впрямь не очень тривиально )
https://godbolt.org/z/515arMxbs

Страницы: 1 2 Следующая »
ПрограммированиеФорумОбщее

Тема в архиве.