hilbert(dir, -rot, order - 1) ; step(dir); dir = dir - rot; hilbert(dir, rot, order - 1); step(dir) ;

hilbert(dir, rot, order - 1); dir = dir - rot; step(dir);

hilbert(dir, -rot, order - 1);

В действительности переменная dir может принимать и другие значения, вне диапазона 0-3, но в этом случае необходимо брать значение dir по модулю 4.

В листинге 14.2 приведена программа-оболочка и функция step, которая используется в функции hilbert. Эта программа получает в качестве гумента порядок генерируемой кривой Гильберта и выводит список отрезков, указывая для каждого направление перемещения и длину кривой до конца отрезка, а также координаты конца текущего отрезка. Например, для кривой Гильберта второго порядка вывод программы оказывается следующим:

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

ttinclude <stdio.h> ttinclude <stdlib.h>

int X = -1, у = 0; Глобальные переменные int i = 0; Расстояние вдоль кривой

int blen; Длина вывода

void hilbert(int dir, int rot, int order);

void binary(unsigned k, int len, char *s) {

/* Преобразование беззнакового целого к в строку

символов. Результат хранится в строке s длины len.

int i;

s[len] = 0;

for (i = len - 1; i if (k ь 1) s[i] else s[i] = 0; к = к >> 1;

0; 1

void step(int dir) {

char ii[33] , xx[17]

yy[17] ;

switch(dir ь 3) {

case 0: X = X +. 1; break

case 1: у = у + 1; break

case 2: X = X - 1; break

case 3: у = у - 1; break

binaryd, 2*blen, ii) ; binary(x, blen, xx); binary(y, blen, yy);

printf("%5d %s %s %s\n", dir, ii, xx, yy); i = i + 1; Увеличение расстояния

int main(int argc, char *argv[]) { int order;

order = atoi(argvCl]); blen = order;

step(O); Вывод начальной точки hilbert(О, 1, order); return 0;

14.2. Преобразование расстояния вдоль кривой Гильберта в координаты

Для того чтобы найти координаты {х,у) точки, определяемой расстоянием s вдоль кривой Гильберта порядка и, заметим, что старшие два бита 2и-битового числа s определяют, в каком квадранте находится точка. Это происходит потому, что кривая Гильберта любого порядка следует общему шаблону кривой первого порядка. Если два старших бита s равны 00, точка находится где-то в нижнем левом квадранте; 01 указывает на верхний левый квадрант, 10 - правый верхний квадрант, и 11 - нижний правый квадрант. Таким образом, два старших бита 5 определяют старшие биты и-битовых чисел д: и у, как показано ниже.

в любой кривой Гильберта встречаются только четыре из восьми возможных U-образных кривых. Они графически показаны в табл. 14.1, где приведено также отображение двух битов 5 на единичные биты д: и у.

Таблица 14.1. Четыре возможных отображения

Заметим, что на рис. 14.2 во всех случаях U-образная кривая, представленная отображением А (П) становится на следующем уровне детализации U-образной кривой, представленной отображениями В, А, А или D (в зависимости от расстояния от начала исходного отображения А- О, 1, 2 или 3). Аналогично, U-образная кривая, представленная отображением В ( 3), на следующем уровне детализации становится представленной отображениями А, В, В или С (в зависимости от расстояния вдоль исходной кривой - О, 1,2 или 3). Результатом таких наблюдений является табл. 14.2, в которой представлены переходы между состояниями, соответствующими отображениям, показанным в табл. 14.1.

Таблица 14.2. Таблица переходов состояний для вычисления (х,у) ms

Для использования этой таблицы начнем с состояния А. Целое s следует дополнить необходимым количеством нулевых битов слева с тем, чтобы его длина стала равной 2п битов, где и - порядок кривой Гильберта. После этого сканируем попарно биты s слева направо. Первая строка табл. 14.2 означает, что если текущим состоянием является А и сканированная пара битов s равна 00, то мы получаем на выходе (6,0) и переходим к со-