Гильберта кривой (также известный как заполняющей пространство кривой Гильберта ) является непрерывной фрактальной пространственно-заполнения кривой впервые описана немецким математиком Давида Гильберта в 1891 году, [1] как вариант пространства заполнения кривых Пеано , обнаруженных Пеано в 1890 г. [2]
Поскольку он заполняет пространство, его размерность Хаусдорфа равна 2 (точнее, его образ - это единичный квадрат, размерность которого равна 2 в любом определении размерности; его график представляет собой компакт, гомеоморфный замкнутому единичному интервалу, с размерностью Хаусдорфа 2) .
Кривая Гильберта строится как предел кусочно-линейных кривых . Длина -й кривой равна , т. Е. Длина растет экспоненциально с , даже если каждая кривая содержится в квадрате с площадью .
Изображения [ править ]
Вариант, первые три итерации [3]
Приложения и алгоритмы сопоставления [ править ]
Как истинная кривая Гильберта, так и ее дискретные приближения полезны, потому что они дают отображение между одномерным и двумерным пространством, которое довольно хорошо сохраняет локальность. [4] Это означает, что две точки данных, которые расположены близко друг к другу в одномерном пространстве, также оказываются близко друг к другу после сворачивания. Обратное не всегда может быть правдой.
Благодаря этому свойству локальности кривая Гильберта широко используется в информатике. Например, диапазон IP-адресов, используемых компьютерами, можно отобразить на картинке с помощью кривой Гильберта. Код для создания изображения будет отображать из 2D в 1D, чтобы найти цвет каждого пикселя, и иногда используется кривая Гильберта, потому что она удерживает ближайшие IP-адреса рядом друг с другом на изображении. [5]
Полутоновой фотография может быть преобразован в колебались черно-белое изображение , используя пороговую, с количеством оставшегося от каждого пикселя добавляется к следующему пикселю вдоль кривой Гильберта. Код для этого будет отображать из 1D в 2D, и иногда используется кривая Гильберта, потому что она не создает отвлекающих шаблонов, которые были бы видны глазу, если бы порядок был просто слева направо по каждой строке пикселей. Кривые Гильберта в более высоких измерениях являются примером обобщения кодов Грея и иногда используются для аналогичных целей по тем же причинам. Для многомерных баз данных было предложено использовать порядок Гильберта вместо Z-порядка.потому что он лучше сохраняет местность. Например, кривые Гильберта использовались для сжатия и ускорения индексов R-дерева [6] (см. R-дерево Гильберта ). Они также использовались для сжатия хранилищ данных. [7] [8]
Учитывая разнообразие приложений, полезно иметь алгоритмы для отображения в обоих направлениях. Во многих языках это лучше, если реализовывать итерацию, а не рекурсию. Следующий код C выполняет сопоставления в обоих направлениях, используя итерацию и битовые операции, а не рекурсию. Он предполагает квадрат, разделенный на n на n ячеек, для n степень 2, с целыми координатами, с (0,0) в нижнем левом углу, ( n - 1, n - 1) в верхнем правом углу и расстояние d, которое начинается с 0 в левом нижнем углу и продолжается дов правом нижнем углу. Это отличается от показанной выше анимации, где кривая начинается в верхнем левом углу и заканчивается в правом верхнем углу.
// конвертируем (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 ); rot ( n , & 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 ; для ( s = 1 ; s < n ; s * = 2 ) { rx = 1 & (т / 2 ); ry = 1 & ( t ^ rx ); rot ( s , x , y , rx , ry ); * х + = s * rx ; * y + = s * ry ; т / = 4 ; } }// повернуть / перевернуть квадрант соответствующим образом void rot ( int n , int * x , int * y , int rx , int ry ) { if ( ry == 0 ) { if ( rx == 1 ) { * x = n - 1 - * х ; * y = n -1 - * y ; } // Меняем местами x и y int t = * x ; * х = * у ; * y = t ; } }
Они используют соглашения C: символ & - это побитовое И, символ ^ - это побитовое исключающее ИЛИ, оператор + = добавляет к переменной, а оператор / = делит переменную. Обработка булевы в средствах C , что в xy2d, переменная гх имеет значение 0 или 1 , чтобы соответствовать немного ы из х , и аналогично для 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 он начинается снизу с ячеек и работает вплоть до включения всего квадрата.
Можно эффективно реализовать кривые Гильберта, даже если пространство данных не образует квадрат. [9] Кроме того, существует несколько возможных обобщений кривых Гильберта на более высокие измерения. [10] [11]
Представление как система Линденмайера [ править ]
Кривая Гильберта может быть выражена системой перезаписи ( L-системой ).
- Алфавит : A, B
- Константы : F + -
- Аксиома : А
- Правила производства :
- А → + BF − AFA − FB +
- B → −AF + BFB + FA−
Здесь «F» означает «рисовать вперед», «+» означает «повернуть налево на 90 °», «-» означает «повернуть направо на 90 °» (см. Графику с черепахой ), а «A» и «B» игнорируются во время рисования. .
Другие реализации [ править ]
Graphics Gems II [12] обсуждает согласованность кривой Гильберта и обеспечивает реализацию.
Кривая Гильберта обычно используется при рендеринге изображений или видео. Обычные программы, такие как Blender и Cinema 4D, используют кривую Гильберта для отслеживания объектов и визуализации сцены.
См. Также [ править ]
Викискладе есть медиафайлы, связанные с кривой Гильберта . |
- Планирование кривой Гильберта
- R-дерево Гильберта
- Местонахождение ссылки
- Хеширование с учетом местоположения
- Кривая Мура
- Многоугольник Мюррея
- Кривая Серпинского
- Список фракталов по размерности Хаусдорфа
Заметки [ править ]
- ^ Д. Гильберта: Über умереть stetige Abbildung Einer Linie ауф Эйн Flächenstück. Mathematische Annalen 38 (1891), 459–460.
- ^ G.Peano: Sur UNE Courbe, кви remplit Toute ипе Aire самолет. Mathematische Annalen 36 (1890), 157–160.
- ^ Бурж, Паскаль. « Глава 1: фракталы », Fractales et chaos . Дата обращения: 9 февраля 2019 г.
- ^ Луна, B .; Джагадиш, HV; Faloutsos, C .; Saltz, JH (2001), «Анализ свойств кластеризации кривой заполнения гильбертова пространства», IEEE Transactions on Knowledge and Data Engineering , 13 (1): 124–141, CiteSeerX 10.1.1.552.6697 , doi : 10.1109 / 69,908985.
- ^ «Отображение всего Интернета с кривыми Гильберта» . blog.benjojo.co.uk . Проверено 2 января 2021 .
- ^ И. Камель, К. Фалаутсос, 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 .
- ^ Гамильтон, Швейцария; Рау-Чаплин А. (2007). «Компактные индексы Гильберта: кривые, заполняющие пространство для областей с неравными длинами сторон». Письма об обработке информации . 105 (5): 155–163. DOI : 10.1016 / j.ipl.2007.08.034 .
- ^ Альбер, Дж .; Нидермайер, Р. (2000). «О многомерных кривых со свойством Гильберта». Теория вычислительных систем . 33 (4): 295–312. CiteSeerX 10.1.1.7.2039 . DOI : 10.1007 / s002240010003 . S2CID 788382 .
- ^ HJ Haverkort, F. van Walderveen, Четырехмерные кривые Гильберта для R-деревьев, в: Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments, 2009, pp. 63–73.
- ^ Вурхис, Дуглас: кривые заполнения пространства и мера когерентности, стр. 26–30, Graphics Gems II.
Дальнейшее чтение [ править ]
- Уоррен-младший, Генри С. (2013). Восторг хакера (2-е изд.). Эддисон Уэсли - ISBN Pearson Education, Inc. 978-0-321-84268-8.
- Маккенна, Дуглас М. (2019). Кривые Гильберта: вовнутрь и вовнутрь . ISBN компании Mathemaesthetics, Inc. 978-1-7332188-0-1.
Внешние ссылки [ править ]
- Динамическая кривая Гильберта с JSXGraph
- Демонстрация трехмерной кривой Гильберта Three.js WebGL
- Мультфильм XKCD, использующий свойства локальности кривой Гильберта для создания «карты Интернета»
- Генератор Gcode для кривой Гильберта
- Итерационный алгоритм рисования кривой Гильберта в JavaScript
- Алгоритм 781: создание кривой заполнения пространства Гильберта с помощью рекурсии (цифровая библиотека ACM)