Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Первые шесть итераций кривой Гильберта

Гильберта кривой (также известный как заполняющей пространство кривой Гильберта ) является непрерывной фрактальной пространственно-заполнения кривой впервые описана немецким математиком Давида Гильберта в 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-дерево Гильберта
  • Местонахождение ссылки
  • Хеширование с учетом местоположения
  • Кривая Мура
  • Многоугольник Мюррея
  • Кривая Серпинского
  • Список фракталов по размерности Хаусдорфа

Заметки [ править ]

  1. ^ Д. Гильберта: Über умереть stetige Abbildung Einer Linie ауф Эйн Flächenstück. Mathematische Annalen 38 (1891), 459–460.
  2. ^ G.Peano: Sur UNE Courbe, кви remplit Toute ипе Aire самолет. Mathematische Annalen 36 (1890), 157–160.
  3. ^ Бурж, Паскаль. « Глава 1: фракталы », Fractales et chaos . Дата обращения: 9 февраля 2019 г.
  4. ^ Луна, 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.
  5. ^ «Отображение всего Интернета с кривыми Гильберта» . blog.benjojo.co.uk . Проверено 2 января 2021 .
  6. ^ И. Камель, К. Фалаутсос, R-дерево Гильберта: улучшенное R-дерево с использованием фракталов, в: Труды 20-й Международной конференции по очень большим базам данных, Morgan Kaufmann Publishers Inc., Сан-Франциско, Калифорния, США, 1994 С. 500–509.
  7. ^ Eavis, T .; Куэва, Д. (2007). Архитектура сжатия гильбертова пространства для сред хранилищ данных . Конспект лекций по информатике . 4654 . С. 1–12. DOI : 10.1007 / 978-3-540-74553-2_1 . ISBN 978-3-540-74552-5.
  8. ^ Лемир, Даниэль; Касер, Оуэн (2011). «Изменение порядка столбцов для меньших индексов». Информационные науки . 181 (12): 2550–2570. arXiv : 0909.1346 . DOI : 10.1016 / j.ins.2011.02.002 . S2CID 15253857 . 
  9. ^ Гамильтон, Швейцария; Рау-Чаплин А. (2007). «Компактные индексы Гильберта: кривые, заполняющие пространство для областей с неравными длинами сторон». Письма об обработке информации . 105 (5): 155–163. DOI : 10.1016 / j.ipl.2007.08.034 .
  10. ^ Альбер, Дж .; Нидермайер, Р. (2000). «О многомерных кривых со свойством Гильберта». Теория вычислительных систем . 33 (4): 295–312. CiteSeerX 10.1.1.7.2039 . DOI : 10.1007 / s002240010003 . S2CID 788382 .  
  11. ^ HJ Haverkort, F. van Walderveen, Четырехмерные кривые Гильберта для R-деревьев, в: Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments, 2009, pp. 63–73.
  12. ^ Вурхис, Дуглас: кривые заполнения пространства и мера когерентности, стр. 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)