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

редактировать

Первые шесть итераций кривой Гильберта

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

Поскольку он заполняет пространство, его размерность Хаусдорфа равна 2 (точнее, его образ - единичный квадрат, размерность которого равна 2 в любом определении размерности; его график - компакт, гомеоморфный замкнутому единичному интервалу, с размерностью Хаусдорфа 2).

$H n {\ displaystyle H_ {n}}$ $H_ {n}$ - $n {\ displaystyle n}$ $n$ -е приближение к предельной кривой. Евклидова длина из $H n {\ displaystyle H_ {n}}$ $H_ {n}$ равна $2 n - 1 2 n {\ displaystyle \ textstyle 2 ^ {n} - {1 \ over 2 ^ {n}}}$ $\ textstyle 2 ^ n - {1 \ over 2 ^ n}$ , т. Е. Он растет экспоненциально с $n {\ displaystyle n}$ $n$ , в то же время всегда ограничиваясь квадрат с конечной площадью.

Содержание

1 Изображения
2 Приложения и алгоритмы сопоставления
3 Представление в виде системы Линденмайера
4 Другие реализации
5 См. Также
6 Примечания
7 Дополнительная литература
8 Внешние ссылки

Изображения

Кривая Гильберта, первый порядок
Кривые Гильберта, первый и второй порядки
Кривые Гильберта, первый-третий порядки
Правила производства
Кривая Гильберта, цвет построения- coded
Трехмерная кривая Гильберта с цветом, показывающим прогрессию
Вариант, первые три итерации
Фотография Дэвида Гильберта с седьмым порядком кривой Гильберта.

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

Как истинная кривая Гильберта, так и ее дискретные приближения полезны, потому что они дают отображение между одномерным и двухмерным пространством, которое довольно хорошо сохраняет локальность. Это означает, что две точки данных, которые расположены близко друг к другу в одномерном пространстве, также будут близки друг к другу после сворачивания. Обратное не всегда может быть правдой.

Благодаря этому свойству локальности кривая Гильберта широко используется в информатике. Например, диапазон IP-адресов, используемых компьютерами, можно отобразить на картинке с помощью кривой Гильберта. Код для создания изображения будет преобразовывать из 2D в 1D, чтобы найти цвет каждого пикселя, и иногда используется кривая Гильберта, потому что она удерживает ближайшие IP-адреса рядом друг с другом на изображении.

A фотографию в оттенках серого можно преобразовать в черно-белое изображение с размытием , используя пороговую обработку, с добавлением остатка от каждого пикселя к следующему пикселю вдоль кривой Гильберта. Код для этого будет отображать из 1D в 2D, и иногда используется кривая Гильберта, потому что она не создает отвлекающих шаблонов, которые были бы видны глазу, если бы порядок был просто слева направо по каждой строке пикселей. Кривые Гильберта в более высоких измерениях являются примером обобщения кодов Грея и иногда используются для аналогичных целей по аналогичным причинам. Для многомерных баз данных было предложено использовать порядок Гильберта вместо Z-порядка, потому что он лучше сохраняет локальность. Например, кривые Гильберта использовались для сжатия и ускорения индексов R-дерева (см. R-дерево Гильберта ). Они также использовались для сжатия хранилищ данных.

Учитывая разнообразие приложений, полезно иметь алгоритмы для сопоставления в обоих направлениях. Во многих языках лучше реализовывать итерацию, а не рекурсию. Следующий код C выполняет сопоставления в обоих направлениях, используя итерацию и битовые операции, а не рекурсию. Он предполагает квадрат, разделенный на n на n ячеек, для степени n степени 2, с целыми координатами, с (0,0) в нижнем левом углу, (n - 1, n - 1) в верхнем правом углу и расстояние d, которое начинается с 0 в нижнем левом углу и продолжается до $n 2-1 {\ displaystyle n ^ {2} -1}$ $n^2-1$ в нижнем правом углу. Это отличается от показанной выше анимации, где кривая начинается с верхнего левого угла и заканчивается в верхнем правом углу.

// конвертируем (x, y) в d int xy2d (int n, int x, int y) {int rx, ry, s, d = 0; для (s = n / 2; s>0; s / = 2) {rx = (x s)>0; ry = (y s)>0; d + = s * s * ((3 * rx) ^ ry); гниль (п, 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; * х = * у = 0; for (s = 1; s Здесь используются соглашения C: символ - это побитовое И, символ ^ - побитовое исключающее ИЛИ, оператор + = добавляет к переменной, а оператор / = делит переменную. Обработка логических значений в C означает, что в xy2d для переменной rx установлено значение 0 или 1, чтобы соответствовать биту s x, и аналогично для ry.
Функция xy2d работает сверху вниз, начиная с самых старшие биты x и y и сначала создают старшие биты d. Функция d2xy работает в обратном порядке, начиная с младших битов d и наращивая x и y, начиная с младших битов. Оба функции используют функцию поворота, чтобы соответствующим образом повернуть и перевернуть систему координат (x, y).
Два алгоритма сопоставления работают одинаково. Весь квадрат рассматривается как состоящий из 4 областей, расположенных 2 на 2. Каждая область состоит из 4 меньших областей и т. Д. Для ряда уровней. На уровне s каждая область имеет s на s ячеек. Имеется один цикл FOR. который проходит через уровни. На каждой итерации сумма добавляется к d или к x и y, в зависимости от того, в какой из 4 областей она находится на текущем уровне. Текущая область из 4 - это (rx, ry), где rx и ry равны 0 или 1. Таким образом, он потребляет 2 входных бита (либо 2 из d, либо по 1 из x и y) и генерирует два выходных бита.. Он также вызывает функцию вращения, так что (x, y) будет подходящим для следующего уровня на следующей итерации. Для xy2d он начинается с верхнего уровня всего квадрата и продвигается вниз до самого нижнего уровня отдельных ячеек. Для d2xy он начинается снизу с ячеек и включает весь квадрат.
Можно эффективно реализовать кривые Гильберта, даже если пространство данных не образует квадрат. Кроме того, существует несколько возможных обобщений кривых Гильберта на более высокие измерения.
Представление в виде системы Линденмайера
Кривая Гильберта может быть выражена с помощью системы перезаписи (L-система ).
Воспроизвести медиа  Кривая Гильберта на ее шестой итерации Алфавит : A, B
Константы : F + -
Аксиома : A
Правила производства : A → - BF + AFA + FB -
B → + AF - BFB - FA +
Здесь «F» означает «движение вперед», «-» означает «повернуть налево на 90 °. "," + "означает" повернуть направо на 90 ° "(см. рисунок черепахи ), а" A "и" B "игнорируются во время рисования.
Другие реализации
Graphics Gems II обсуждает когерентность кривой Гильберта и предоставляет реализацию.
Кривая Гильберта обычно используется при визуализации изображений или видео. Обычные программы, такие как Blender и Cinema 4D, используют кривую Гильберта для отслеживания объектов и визуализации сцены.
См. Также
На Викискладе есть материалы, связанные с кривой Гильберта.
Планирование кривой Гильберта 
R-дерево Гильберта 
Местонахождение ссылки 
С учетом особенностей местности хеширование 
кривая Мура 
многоугольник Мюррея 
кривая Серпинского 
Список фракталов по размерности Хаусдорфа 
Примечания
^D. Гильберт: Über die stetige Abbildung einer Linie auf ein Flächenstück. Mathematische Annalen 38 (1891), 459–460.
^Г.Пеано: Sur une courbe, qui remplit toute une aire plane. Mathematische Annalen 36 (1890), 157–160.
^Бурж, Паскаль. «Глава 1: фракталы », Fractales et chaos. Доступ: 9 февраля 2019 г.
^Moon, B.; Jagadish, H.V.; Faloutsos, C.; Зальц, Дж. (2001), «Анализ свойств кластеризации кривой заполнения гильбертова пространства», IEEE Transactions on Knowledge and Data Engineering, 13 (1): 124–141, CiteSeerX 10.1.1.552.6697, doi : 10.1109 / 69.908985.
^I. Камел, К. Фалаутсос, R-дерево Гильберта: улучшенное R-дерево с использованием фракталов, в: Труды 20-й Международной конференции по очень большим базам данных, Morgan Kaufmann Publishers Inc., Сан-Франциско, Калифорния, США, 1994, стр. 500–509.
^Eavis, T.; Куева, Д. (2007). Архитектура сжатия гильбертова пространства для сред хранилищ данных. Конспект лекций по информатике. 4654 . С. 1–12. DOI : 10.1007 / 978-3-540-74553-2_1. ISBN 978-3-540-74552-5.
^Лемир, Даниэль; Касер, Оуэн (2011). «Изменение порядка столбцов для меньших индексов». Информационные науки. 181 (12): 2550–2570. arXiv : 0909.1346. doi : 10.1016 / j.ins.2011.02.002. S2CID 15253857.
^Hamilton, C.H.; Рау-Чаплин А. (2007). «Компактные индексы Гильберта: кривые, заполняющие пространство для областей с неравными длинами сторон». Письма об обработке информации. 105 (5): 155–163. doi : 10.1016 / j.ipl.2007.08.034.
^Alber, J.; Нидермайер, Р. (2000). «О многомерных кривых со свойством Гильберта». Теория вычислительных систем. 33 (4): 295–312. CiteSeerX 10.1.1.7.2039. doi : 10.1007 / s002240010003. S2CID 788382.
^H. Дж. Хаверкорт, Ф. ван Вальдервин, Четырехмерные кривые Гильберта для R-деревьев, в: Труды одиннадцатого семинара по разработке алгоритмов и экспериментам, 2009, стр. 63–73.
^Вурхис, Дуглас: кривые заполнения пространства и мера когерентности, стр. 26–30, Graphics Gems II.
Дополнительная литература
Уоррен-младший, Генри С. (2013). Восторг хакера (2-е изд.). Эддисон Уэсли - Pearson Education, Inc. ISBN 978-0-321-84268-8.
Маккенна, Дуглас М. (2019). Кривые Гильберта: снаружи внутрь и внутрь. Mathemaesthetics, Inc. ISBN 978-1-7332188-0-1.
Внешние ссылки
Динамическая кривая Гильберта с JSXGraph 
Демонстрация трехмерной кривой Гильберта Three.js WebGL 
Мультфильм XKCD, использующий свойства локальности кривой Гильберта для создания «карты Интернета» 
Генератор G-кода для кривой Гильберта 
Итерационный алгоритм для рисования кривой Гильберта в JavaScript 
Алгоритм 781: создание кривой заполнения пространства Гильберта рекурсией (Цифровая библиотека ACM) 
.