Перенумеровать ячейки таблицы NxN

mitgor

Дана таблица NxN, N = 2^k, k = 1, ...
Не могу подобрать оптимальную формулу для преобразования одного способа нумерования в другой:

лучшее что придумал - итеративный способ, например из второго в первый:
 
int n2_to_n1(int n2, int k)
{
int halfsize = 2 ^ (k - 1);
int halfarea = halfsize * halfsize;
int size = halfsize * 2;
int x = n2 % size; // координата по х
int y = n2 / size; // координата по у
n1 = 0;
for (int iter = k; iter > 0; ++iter)
{
n1 += halfarea * (2*y / halfsize + y / halfsize);
x = x % halfsize;
y = y % halfsize;
halfsize = halfsize / 2;
halfarea = halfarea / 4;
}

, нечто похожее - обратно.
Нет ли какой-нибудь прямой формулы?

mitgor

Ну, например, при том же увеличении N в 2^k раз, предыдущие элементы не поменяют свой номер.
А еще зная номер элемента в такой матрице - можно вычислить его позицию в downsampled матрице просто сдвинув номер на нужную степень downsampling.
Не для массового использования, конечно.
И почему это говно? Я же не заставляю тебя это где-то применять, а просто спрашиваю совета.

Martika1

Сюда глянь, тут что-то подобное: http://msdn.microsoft.com/en-us/library/bb259689.aspx
Кстати, бувально сегодня передо мной встала смежная задача: найти номера соседей ячейки по её номеру в такой "системе координат".

Damrad

так-то да. но зачем свой способ было придумывать? есть же zigzag-way, как в jpeg
Или как тут на 6той странице
http://jpegclub.org/temp/ITU-T-JPEG-Plus-Proposal_R3.doc

antcatt77

x,y-представление:
 введем промежуточное представление в виде x, y:
   x - координата по горизонтали, отсчет с нуля, слева направо
   y - координата по вертикали, отсчет с нуля, снизу вверх
 
фрактальный порядок:
 левый порядок назовем фрактальным порядком.
последовательный порядок(по горизонтали):
правый порядок назовем последовательным порядком(по горизонтали)
фрактальный порядок -> x,y представление:
 фрактальный порядок переводится в x,y представление следующим образом:
номер разложить в двоичное представление -
  цифры на четных позициях(при нумерации с 0, начиная с младшей позиции) образуют x,
  цифры на нечетных позициях образуют y
x,y представление -> фрактальный порядок:
   x,y разложить на двоичное представление,
    двоичные цифры x поставить на четные места,
    двоичные цифры y поставить на нечетные места
x,y представление -> последовательный порядок(по горизонтали):
 Ny+x
последовательный порядок(по горизонтали) -> x,y представление:
  x(n mod N y(n div N)

antcatt77

Кстати, бувально сегодня передо мной встала смежная задача: найти номера соседей ячейки по её номеру в такой "системе координат".
Перевести в x,y представление, прибавить/вычесть единицу, перевести обратно.
Перевод туда обратно можно убрать, реализовав операции увеличения(уменьшения) на 1, которые "затрагивают" только четные(или нечетные) биты.

Martika1

так и пришлось сделать. Вероятно, есть более алгоритмически более эффективный способ: поиграть с цифрами, но в моём случае N небольшое, цифр всего 12, так что проще было сдвинуть на единицу.

antcatt77

но в моём случае N небольшое, цифр всего 12, так что проще было сдвинуть на единицу
в смысле сдвинуть на единицу?

Martika1

подсунуть в функцию, возвращающую номер ячейки, помимо нужной координаты (x,y) еще (x+d,y (x,y+d) и (x+d,y+d где d - размер клетки.

mitgor

Да, так и есть. А теперь вопрос к тебе как к программисту, есть ли такая операция, которая позволила бы сделать это в одну строчку? =)
 
  
x =
fractal_coord & 1 +
(fractal_coord & 100) >> 1 +
(fractal_coord & 10000) >> 2 +
(fractal_coord & 1000000) >> 3 +
....
(fractal_coord & (1 << 2k-1) ) >> k -1

эти тысячи и миллионы - бинарные

antcatt77

вообще там формулы получаются простые(условно) для поиска соседей:

var x_mask = 0x5555555;
var y_mask = 0xAAAAAAA;

var right = n & x_mask) + 1 + y_mask) & x_mask) | (n & y_mask);
var up = n & y_mask) + 1 + x_mask) & y_mask) | (n & x_mask);

var left = n & x_mask) - 1) & x_mask) | (n & y_mask);
var down = n & y_mask) - 1) & y_mask) | (n & x_mask);

antcatt77

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

mitgor

черт, да, похоже этого достаточно.
я почему-то хотел избавиться зависимости от k, но, думаю, для 32битных интов можно раскрыть для максимального k.
можно, конечно, еще тимплейты специализировать....
спасибо! думаю вопрос closed

mitgor

Кстати, хорошая тема, и на трехмерный случай тоже ложится. Но мне мой вариант больше подходит в задаче.

antcatt77

можно ускорить через доп. память:

x = hi_x[(n >> 24) & 0xFF] + low_x[(n >> 16) & 0xFF]) << 8) + hi_x[(n >> 8) & 0xFF] + low_x[n & 0xFF]);

low_x - табличное задание функции(в виде массива которая для 8-ми битного значения выкидывает нечетные биты и сдвигает оставшиеся
hi_x(..) = low_x(..) << 4;

mitgor

блиииин. вот на эту шнягу наткнулся недавно
http://en.wikipedia.org/wiki/Z-order_curve
Оставить комментарий
Имя или ник:
Комментарий: