Кривая Гильберта

Поделись знанием:
Перейти к: навигация, поиск

Кривая Гильберта (известная также как заполняющая пространство кривая Гильберта) — это непрерывная фрактальная заполняющая пространство кривая, впервые описанная немецким математиком Давидом Гильбертом в 1891 году[1], как вариант заполняющих пространство кривых Пеано, открытых итальянским математиком Джузеппе Пеано в 1890 году[2].

Поскольку кривая заполняет плоскость, её размерность Хаусдорфа равна <math>2</math> (в точности, её образ является единичным квадратом, размерность которого равна 2 при любом определении размерности, а её граф является компактным множеством, гомеоморфным замкнутому единичному интервалу с хаусдорфовой размерностью 2).

<math>H_n</math> является <math> n </math>-м приближением к предельной кривой. Евклидова длина кривой <math> H_n </math> равна <math>\textstyle 2^n - {1 \over 2^n} </math>, то есть растёт экспоненциально от <math>n</math>, будучи в то же время всегда в пределах квадрата с конечной площадью.





Рисунки

  • Hilbert curve 1.svg

    Кривая Гильберта, первый шаг

  • Hilbert curve 2.svg

    Кривые Гильберта, первый и второй шаги

  • Hilbert curve 3.svg

    Кривые Гильберта, с первого по третий шаги

  • HilbertCurveString.JPG

    Ниточная графика

  • Hilbert.png

    Кривая Гильберта в цвете

  • Hilbert512.gif

    Трёхмерная кривая Гильберта

  • Hilbert3d-step3.png

    Трёхмерная кривая Гильберта в цвете, указывающем последовательность

  • Hilbert Curve Animation.gif

    Анимационная иллюстрация, показывающая прохождение кружков по кривой.

Приложения и алгоритмы отображения

Как истинная кривая Гильберта, так и её дискретная аппроксимация дают отображение одномерного и двумерного пространств, довольно хорошо сохраняющих локальные свойства[3]. Если обозначить через (x, y) координаты точки в единичном квадрате, а через d расстояние вдоль кривой, на котором эта точка достигается, то точки, имеющие близкие к d значения, будут иметь также близкие значения и к (x, y). Обратное не всегда верно — некоторые точки, имеющие близкие координаты (x, y), имеют достаточно большую разницу в расстоянии d.

Ввиду этого свойства локальности кривая Гильберта широко применяется в компьютерных программах. Например, диапазон IP-адресов, присвоенных компьютерам, можно представить в виде рисунка путём использования кривой Гильберта. Программа создания такого представления для определения цвета точек может преобразовать изображение из двумерного в одномерное, и кривая Гильберта иногда используется ввиду свойства локальности этой кривой, поскольку это позволяет сохранять близкие IP-адреса близкими на одномерном представлении. Чёрно-белая фотография может быть подвержена дизерингу при использовании меньшего числа градаций серого путём переноса остаточного значения величины яркости на следующую точку вдоль кривой Гильберта. Кривая Гильберта используется в этом случае, поскольку она не создаёт видимых глазом переходов яркости, которые получаются при построчном преобразовании. Кривые Гильберта в пространствах большей размерности являются представителями обобщений кодов Грея и иногда используются в похожих ситуациях с похожими целями. Для многомерных баз данных предлагается использовать порядок Гильберта вместо Z-порядка[en], поскольку он даёт лучшее сохранение локальности. Например, кривые Гильберта использовались для сжатия и ускорения индексов в виде R-дерева[en][4]. Кривые Гильберта использовались также для сжатия информационных баз данных[5][6].

Полезно иметь алгоритм, позволяющий делать преобразование в обоих направлениях (как из (x, y) в d, так и из d в (x, y)). Во многих языках программирования предпочтительнее использовать итерации, а не рекурсию. Следующая программа на языке C осуществляет отображение в обоих направлениях, используя итерации и битовые операции, а не рекурсию. Программа предполагает разбиение квадрата на n х n ячеек (квадратов со стороной 1), где n является степенью двойки. Координаты (0,0) принадлежат левому нижнему углу, а (n-1, n-1) — правому верхнему углу. Расстояние d отсчитывается от левого нижнего угла (расстояние 0) и растёт до <math>n^2-1</math> в правом нижнем углу. 

//Преобразовать (x,y) к d
int xy2d (int n, int x, int y) {
    int rx, ry, s, d=0;
    for (s=n/2; s>0; s/=2) {
        rx = (x & s) > 0;
        ry = (y & s) > 0;
        d += s * s * ((3 * rx) ^ ry);
        rot(s, &x, &y, rx, ry);
    }
    return d;
}

//Преобразовать d к (x,y)
void d2xy(int n, int d, int *x, int *y) {
    int rx, ry, s, t=d;
    *x = *y = 0;
    for (s=1; s<n; s*=2) {
        rx = 1 & (t/2);
        ry = 1 & (t ^ rx);
        rot(s, x, y, rx, ry);
        *x += s * rx;
        *y += s * ry;
        t /= 4;
    }
}

//вращаем/отражаем квадрант
void rot(int n, int *x, int *y, int rx, int ry) {
    if (ry == 0) {
        if (rx == 1) {
            *x = n-1 - *x;
            *y = n-1 - *y;
        }

        //Обмениваем x и y местами
        int t  = *x;
        *x = *y;
        *y = t;
    }
}

Программа использует соглашения языка C: знак & означает побитную операцию AND (И), знак ^ — побитную XOR (ИЛИ), знак += означает оператор добавления к переменной, а знак /= — операцию деления переменной.

Функция xy2d работает сверху вниз, начиная со старших битов x и y, и начинает построение d со старших битов. Функция d2xy работает в противоположном направлении, начиная с младших битов d, и строит x и y с младших битов. Обе функции используют функцию вращения и отражения системы координат (x, y).

Оба алгоритма работают похожим образом. Весь квадрат рассматривается как 4 области 2 х 2. Каждая область состоит из 4 меньших областей и так далее до конечного уровня. На уровне s каждая область имеет s х s ячеек. Имеется единственный цикл FOR, пробегающий через уровни. На каждой итерации добавляется значение к d или к x и y, которое определяется областью (из четырёх), в которой находимся на данном уровне. Области задаются парой (rx, ry), где rx и ry принимают значение 0 или 1. Таким образом, область определяется 2 входными битами (либо двумя битами из d, либо по биту из x и y), и по ним образуется два выходных бита. Также вызывается функция вращения, чтобы (x, y) можно было использовать на следующем уровне на следующей итерации. Для xy2d она начинается с верхнего уровня всего квадрата и движется вниз до нижнего уровня до индивидуальных ячеек. Для d2xy процесс начинается снизу с ячеек и движется вверх до полного квадрата.

Можно реализовать эффективно кривые Гильберта, даже если область не образует квадрат[7]. Более того, существуют некоторые обобщения кривых Гильберта для более высоких размерностей[8][9].

Представление в системе Линденмайера

Создание кривой Гильберта можно переписать для системы L-System[en].

Алфавит : A, B
Константы : F + −
Аксиома : A
Правила:
A → − B F + A F A + F B −
B → + A F − B F B − F A +

Здесь F означает «движение вперёд», «−» означает поворот влево на 90°, «+» означает поворот вправо на 90° (см. turtle graphics), а A и B игнорируются при рисовании.

Другие реализации

Arthur Butz[10] дал алгоритм вычисления кривой Гильберта в многомерных пространствах.

В книге Graphics Gems II[11] обсуждается кривая Гильберта и даётся реализация.

См. также

Напишите отзыв о статье "Кривая Гильберта"

Примечания

  1. ↑ Hilbert, 1891, с. 459—460.
  2. ↑ Peano, 1890, с. 157—160.
  3. ↑ Moon, Jagadish, Faloutsos, Saltz, 2001, с. 124—141.
  4. ↑ Kamel, Faloutsos, 1994, с. 500—509.
  5. ↑ Eavis, Cueva, 2007, с. 1—12.
  6. ↑ Lemire, Kaser, 2011.
  7. ↑ Hamilton, Rau-Chaplin, 2007, с. 155—163.
  8. ↑ Alber, Niedermeier, 2000, с. 295—312.
  9. ↑ Haverkort, van Walderveen, 2009, с. 63—73.
  10. ↑ Butz, 1971, с. 424—42.
  11. ↑ Voorhies, 1991, с. 26—30.

Литература

  • I. Kamel, C. Faloutsos. Proceedings of the 20th International Conference on Very Large Data Bases / Jorge Bocca, Matthias Jarke, Carlo Zaniolo. — San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1994. — ISBN 1-55860-153-8.
  • G.Peano [www.digizeitschriften.de/dms/img/?PPN=PPN235181684_0036&DMDID=dmdlog13 Sur une courbe, qui remplit toute une aire plane.] // Mathematische Annalen. — 1890. — Вып. 36.
  • D. Hilbert [www.digizeitschriften.de/dms/img/?PPN=PPN235181684_0038&DMDID=dmdlog40 Über die stetige Abbildung einer Linie auf ein Flächenstück.] // Mathematische Annalen. — 1891. — Вып. 38.
  • A.R. Butz Alternative algorithm for Hilbert’s space filling curve. // IEEE Trans. On Computers. — 1971. — Т. 20. — DOI:10.1109/T-C.1971.223258.
  • B. Moon, H.V. Jagadish, C. Faloutsos, J.H. Saltz Analysis of the clustering properties of the Hilbert space-filling curve // IEEE Transactions on Knowledge and Data Engineering. — 2001. — Т. 13, вып. 1. — DOI:10.1109/69.908985.
  • I. Kamel, C. Faloutsos. Proceedings of the 20th International Conference on Very Large Data Bases. — San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1994.
  • T. Eavis, D. Cueva A Hilbert space compression architecture for data warehouse environments // Lecture Notes in Computer Science. — 2007. — Т. 4654.
  • Daniel Lemire, Owen Kaser Reordering Columns for Smaller Indexes // Information Sciences. — 2011. — Т. 181, вып. 12. — arXiv:0909.1346.
  • C. H. Hamilton, A. Rau-Chaplin Compact Hilbert indices: Space-filling curves for domains with unequal side lengths // Information Processing Letters. — 2007. — Т. 105, вып. 5. — DOI:10.1016/j.ipl.2007.08.034.
  • J. Alber, R. Niedermeier On multidimensional curves with Hilbert property // Theory of Computing Systems. — 2000. — Т. 33, вып. 4. — DOI:10.1007/s002240010003.
  • H. J. Haverkort, F. van Walderveen,. Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments. — New York: Society for Industrial and Applied Mathematics ( SIAM ), 2009. — ISBN 9781615671489.
  • Douglas Voorhies. Space-Filling Curves and a Measure of Coherence / Andrew S. Glassner. — Boston, San Diego, New York, London, Sydney, Tokyo, Toronto: AP Professional, 1991. — Т. II. — (Graphics Gems). — ISBN 0-12-059756-X.

Ссылки

  • [jsxgraph.uni-bayreuth.de/wiki/index.php/Hilbert_curve Dynamic Hilbert curve with JSXGraph]
  • [threejs.org/examples/webgl_lines_colors.html Three.js WebGL 3D Hilbert curve demo]
  • [xkcd.com/195/ XKCD cartoon using the locality properties of the Hilbert curve to create a «map of the internet»]
  • [www.andyshelley.co.uk/axishilbert/index.php Gcode generator for Hilbert curve]