ГЛАВА 14 КРИВАЯ ГИЛЬБЕРТА

в 1890 году Джузеппе Пеано (Giuseppe Реапо) открыл плоскую кривую с удивиггель-ным свойством "заполнения пространства". Такая кривая заполняла единичный квадрат и проходила через каждую его точку {х,у) по меньшей мере один раз.

Кривая Пеано основана на разделении каждой стороны единичного квадрата на три равные части, которые делят его на девять меньших квадратов. Кривая проходит эти девять квадратов в определенном порядке. Затем каждый из девяти малых квадратов аналогично делится на девять частей, и кривая модифищфуется таким образом, чтобы обойти все части в определенном порядке. Эта кривая может быть описана с использованием дробных чисел, записанных в системе счисления по основанию 3; Пеано описал ее впервые именно так.

В 1891 году Давид Гильберт (David Hilbert) [28] открыл вариант кривой Пеано, основанной на делении каждой стороны единичного квадрата иа две равные части, что делит квадрат на четыре меньшие части. Затем каждый из четырех получившихся квадратов, в свою очередь, аналогично делится на четыре меньших квадрата и т.д. На каждой стадии такого деления Гильберт строил кривую, которая обходила все имеющиеся квадраты. Кривая Гильберта (которую иногда называют кривой Пеано-Гильберта) представляет собой предельную кривую, полученную в результате такого построения. Ее можно описать с помощью дробей, записанных в системе счисления по основанию 2.

На рис. 14.1 показаны первые три шага последовательности, приводящей к получению заполняющей пространство кривой Гильберта, в том виде, в котором они были показаны в его статье в 1891 году.

Рис. 14.1. Первые три кривые в последовательности, определяющей кривую Гильберта

Здесь мы поступим немного иначе. Используем термин "кривая Гильберта" ддя любой кривой из последовательности построения заполняющей пространство кривой Гильберта, и под "кривой Гильберта и-го порядка" будет подразумеваться и-я кривая последовательности (на рис. 14.1 показаны кривые первого, второго и третьего порядков). Каждая кривая порядка и масштабируется множителем 2" с тем, чтобы координаты углов кривой представляли собой целые числа. Таким образом, наша кривая Гильберта порядка и имеет углы с координатами от О до 2" -1 по осям х и у. Примем положительным направление вдоль кривой от точки (х,у) = (0,0) к (2" -1,0). На рис. 14.2 показаны рассматриваемые нами

масштабированные кривые Гильберта от первого до шестого порядка.

Напомним - кривая представляет собой непрерывное отображение одномерного пространства на л-мерное.

0 1 0 3

О 7 0

Н]3 SP5 5 5{й Щ

&5]3 й{й 5 &та

Рмс. 74.2. Кривые Гильберта порядка 1-6

Для того чтобы понять, каким образом строится кривая Гильберта, рассмотрим внимательно кривые на рис. 14.2. Кривая порядка 1 состоит из отрезков, направленных вверх, вправо и вниз. Кривая порядка 2 следует тому же общему щаблону. Сначала изображается U-образная кривая, идущая вверх, затем от нее вверх идет отрезок, который соединяется с очередной U-образной кривой, направленной вправо. От нее идет отрезок вправо, к такой же U-образной кривой, от которой отрезок вниз ведет нас к последней U-образной кривой, ведущей вниз. В результате из перевернутой U-образной кривой первого порядка будет получена Y-образная кривая второго порядка.

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

Преобразование кривой Гильберта первого порядка (кривая U с общим направлением вправо и вращательной ориентацией по часовой стрелке) в кривую второго порядка происходит следующим образом.

1. Рисуем и по направлению вверх против часовой стрелки.

2. Рисуем отрезок, направленный вверх.

3. Рисуем и по направлению вправо по часовой стрелке.

4. Рисуем отрезок, направленный вправо.

5. Рисуем и по направлению вправо по часовой стрелке.

6. Рисуем отрезок, направленный вниз.

7. Рисуем и по направлению вниз против часовой стрелки.

Рассматривая кривые разных порядков, можно видеть, что все U, ориентированные так же, как и в кривой Гильберта первого порядка, трансформируются таким же образом. Сходный набор правил трансформации может быть создан для каждой U-образной кривой с другой ориентацией. Все эти правила легко укладываются в рекурсивную программу построения кривой Гильберта, показанную в листинге 14.1 [58]. В приведенной программе ориентация U характеризуется двумя целыми числами, которые определяют направление и вращательное направления следующим образом:

dir = О: вправо rot = +1: по часовой стрелке

dir = 1: вверх rot = -1 : против часовой стрелки

dir = 2: влево dir = 3: вниз

Листинг 14.1. Генерация кривой Гильберта

void step(int);

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

if (order == 0) return; dir = dir + rot;

14.1. РЕКУРСИВНЫЙ АЛГОРИТМ ПОСТРОЕНИЯ КРИВОЙ ГИЛЬБЕРТА 235