в [44] приведен алгоритм дяя вьмисления s по значениям (х,у), похожий на соответствующий апгориш для вычислений в обратном направлении - {х,у) по значению s. Этот алгоритм основан на сканировании слева направо и показан в табл. 14.6 и листинге 14.7.

Таблица 14.6. Метод вычисления s по значениям (х,у) [44]

Листинг 14.7. Метод вычисления s по значениям (х,у) [44] unsigned hil s from xy(unsigned х,

unsigned у, int n)

int i, xi, yi; unsigned s, temp; s = 0;

for (i = n - 1; i >= 0; i--) { xi = (x » i) Ь 1; yi = (y >> i) Ь 1; if (yi == 0) { temp = X;

X = y*(-xi); у = temp*(-xi);

s = 4*s + 2*xi + (xi*yi)

return s;

Инициализация

Получаем i-й бит x Получаем i-й бит у

Обмениваем х и у и, если xi = 1, дополняем их

Добавляем два бита к s

14.4. Увеличение координат кривой Гильберта

Пусть заданы координаты (д:, у) точки на кривой Гильберта и-го порядка. Каким образом

можно найти координаты следующей точки? Простейший путь, конечно, состоит в преобразовании координат в расстояние вдоль кривой s, увеличении .у на 1 и обратном преофазова-нии в координаты (д:, у) с использованием описанньк в предьщущих разделах алгоритмов.

Более удачный (но не слишком) путь основывается на том факте, что при перемещении вдоль кривой Гильберта на каждом шаге или х, или у, но не обе величины одновременно либо увеличиваются, либо уменьшаются на 1. Поэтому можно разработать алгоритм, который сканирует координаты слева направо для определения того, какой тип U-образной кривой представляют собой младшие два бита. Затем на основании этой информации и значения двух младших битов осуществляется увеличение или уменьшение х или у.

В данном алгоритме есть сложность, возникающая на каждом четвертом шаге, когда рассматриваемая точка оказывается в конце U-образной кривой. В этой точке

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

Этот алгоритм описывается табл. 14.7, где А, В, С и D обозначают U-образные кривые, показанные в табл. 14.1. Для использования данной таблицы сначала надо добавить к д: и у ведущие нулевые биты с тем, чтобы получились и-битовые значения (где и - порядок рассматриваемой кривой Гильберта). Начиная с состояния А, сканируем биты д: и у слева направо. Первая строка табл. 14.7 означает, что если текущим состоянием является А, а сканированы биты (0,0), то надо установить перемен-иую-флаг, указывающую необходимость увеличения у, и перейти в состояние В. Прочие строки таблицы интерпретируются аналогично; суффикс "минус" означает, что соответствующая координата должна быть уменьшена. Прочерк в третьем столбце таблицы говорит о том, что переменная-флаг, отслеживающая изменение координат, остается на данном шаге неизменной.

По окончании сканирования битов д: и у увеличиваем (или уменьшаем) значение одной из координат в соответствии со значением переменной-флага.

Таблица 14.7. Добавление одного звена кривой Гильберта

Программа на языке С, реализующая рассмотренный алгоритм, представлена в листинге 14.8. Переменная dx инициализируется таким образом, чтобы при многократных вызовах данной функции в цикле генерировалась одна кривая Гильберта.

Листинг 14.8. Программа для добавления одного звена кривой Гильберта

void hil inc xy(unsigned *хр, unsigned *ур, int n) {

int i;

unsigned x, y, state, dx, dy, row, dochange; X = *xp; У = *YP;

state = 0; Инициализация

dx = -((1 « n) -1); -(2**n - 1) dy = 0;

for (i = n-1; i >= 0; i--) { Выполняем n раз row = 4*state 2* ( (x » i) ь 1) (y » i) ь 1; dochange = (OxBDDB » row) & 1; if (dochange) {

dx = ((0x16451659 » 2*row) & 3) - 1;

dy = ((0x51166516 » 2*row) ь 3) - 1;

state = (Ox8FE65e31 >> 2*row) & 3;

*xp = *xp + dX; *yp = *yp + dy;

Табл. 14.7 легко реализуется представленной на рис. 14.4 логикой. На этом рисунке использованы приведенные ниже обозначения.

дг, г-й бит входного значения х у, (-Й бит входного значения у

X, Y Обмененные и дополненные в соответствии со значениями

и С,+1 значения xi и у, / Флаг: если равен 1 - увеличение на 1, если О - уменьшение на 1 W Флаг: если равен 1, увеличивается или уменьшается д;,

если О - увеличивается или уменьшается у S Если значение S равно 1, выполняется обмен х, и у, С Если значение С равно 1, выполняется дополнение Xj и у,

Пары значений 5 и С определяют состояние в табл. 14.7: пары {S,C), равные (0,0), (0,1),

(1,0) и (1,1), обозначают соответственно состояния А, В, С и D. Выходные сигналы /о и Wo указывают, должно ли выполняться уменьшение или увеличение координаты и какой именно. (В дополнение к указанной на рисунке логике требуется схема увеличения/уменьшения с мультиплексорами, указывающими, какое именно значение - х или у - должно быть увеличено или уменьшено, а также схема, которая поместит вычисленное значение назад в регистр, где хранится переменная х или у. В качестве альтернативы можно обойтись двумя схемами увеличения/уменьшения.)