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

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

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

Кривая Гильберта строится как предел кусочно-линейных кривых . Длина $n$ эта кривая $\textstyle 2^{n}-{1 \over 2^{n}}$ , т. е. длина растет экспоненциально с увеличением $n$ , хотя каждая кривая содержится в квадрате площадью $1$ .

Изображения [ править ]

Кривая Гильберта первого порядка
Кривые Гильберта первого и второго порядков.
Кривые Гильберта первого-третьего порядков
Правила производства
Кривая Гильберта, построение имеет цветовую маркировку
Трехмерная кривая Гильберта с цветом, показывающим прогресс.
Вариант, первые три итерации ^[3]

Приложения и алгоритмы картографии [ править ]

И истинная кривая Гильберта, и ее дискретные аппроксимации полезны, поскольку они дают отображение между одномерным и двумерным пространством, которое довольно хорошо сохраняет локальность. ^[4] Это означает, что две точки данных, которые находятся близко друг к другу в одномерном пространстве, также близки друг к другу после свертывания. Обратное не всегда может быть верным.

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

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

Линейное расстояние любой точки вдоль кривой можно преобразовать в координаты в n измерениях для заданного n и наоборот, используя любой из нескольких стандартных математических методов, таких как метод Скиллинга. ^[12]^[13]

Можно эффективно реализовать кривые Гильберта, даже если пространство данных не образует квадрат. ^[14] Более того, существует несколько возможных обобщений кривых Гильберта на более высокие измерения. ^[15]^[16]

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

Кривая Гильберта может быть выражена с помощью системы перезаписи ( L-системы ).

Кривая Гильберта на шестой итерации

Алфавит : А, Б

Константы : F + −

Аксиома : А

Правила производства :

А → +БФ-АФА-ФБ+

Б → −AF+BFB+FA−

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

Другие реализации [ править ]

Графические драгоценности II ^[17] обсуждает когерентность кривой Гильберта и обеспечивает реализацию.

Кривая Гильберта обычно используется при рендеринге изображений или видео. Обычные программы, такие как Blender и Cinema 4D, используют кривую Гильберта для трассировки объектов и рендеринга сцены. ^{[ нужна ссылка ]}

Программное обеспечение слайсера, используемое для преобразования 3D-моделей в траектории движения инструмента для 3D-принтера, обычно имеет кривую Гильберта в качестве опции для шаблона заполнения.

См. также [ править ]

Примечания [ править ]

^ Д. Гильберт: О непрерывном отображении линии на поверхность. Математические анналы 38 (1891), 459–460.
^ Г.Пеано: На кривой, заполняющей всю плоскую область. Mathematische Annalen 36 (1890), 157–160.
^ Бурж, Паскаль. « Глава 1: Фракталы », Фракталы и хаос . Доступ: 9 февраля 2019 г.
^ Мун, Б.; Джагадиш, Х.В.; Фалуцсос, К.; Сальц, Дж. Х. (2001), «Анализ свойств кластеризации кривой заполнения пространства Гильберта», IEEE Transactions on Knowledge and Data Engineering , 13 (1): 124–141, CiteSeerX 10.1.1.552.6697 , doi : 10.1109/ 69.908985 , S2CID 728511 .
^ «Отображение всего Интернета с помощью кривых Гильберта» . blog.benjojo.co.uk . Проверено 02 января 2021 г.
^ Спайрс, Шеннон В.; Голдсмит, Стивен Ю. (1998), Дрогул, Алексис; Тамбе, Милинд; Фукуда, Тосио (ред.), «Исчерпывающий географический поиск с помощью мобильных роботов по кривым, заполняющим пространство» , Collective Robotics , vol. 1456, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 1–12, doi : 10.1007/bfb0033369 , ISBN 978-3-540-64768-3 , получено 14 августа 2023 г.
^ Садат, Сейед Аббас; Ваверла, Йенс; Воган, Ричард (2015). Фрактальные траектории для онлайн-неравномерного воздушного покрытия . Международная конференция IEEE по робототехнике и автоматизации (ICRA), 2015 г. стр. 2971–2976.
^ Тиадмер Риемерсма (1 декабря 1998 г.). «Техника сбалансированного дизеринга» . Журнал пользователя C/C++ . Доктор Добб.
^ И. Камель, К. Фалуцос, R-дерево Гильберта: улучшенное R-дерево с использованием фракталов, в: Материалы 20-й Международной конференции по очень большим базам данных, Morgan Kaufmann Publishers Inc., Сан-Франциско, Калифорния, США, 1994. , стр. 500–509.
^ Ивис, Т.; Куэва, Д. (2007). «Архитектура сжатия гильбертового пространства для сред хранилищ данных». Хранилище данных и обнаружение знаний . Конспекты лекций по информатике. Том. 4654. стр. 1–12. дои : 10.1007/978-3-540-74553-2_1 . ISBN 978-3-540-74552-5 .
^ Лемир, Дэниел; Касер, Оуэн (2011). «Переупорядочение столбцов для меньших индексов». Информационные науки . 181 (12): 2550–2570. arXiv : 0909.1346 . дои : 10.1016/j.ins.2011.02.002 . S2CID 15253857 .
^ Программирование кривой Гильберта Джона Скиллинга
^ Грант Теббин: Расчет координат кривой Гильберта
^ Гамильтон, Швейцария; Рау-Чаплин, А. (2007). «Компактные индексы Гильберта: кривые, заполняющие пространство для областей с неравными длинами сторон». Письма об обработке информации . 105 (5): 155–163. дои : 10.1016/j.ipl.2007.08.034 .
^ Альбер, Дж.; Нидермайер, Р. (2000). «О многомерных кривых со свойством Гильберта». Теория вычислительных систем . 33 (4): 295–312. CiteSeerX 10.1.1.7.2039 . дои : 10.1007/s002240010003 . S2CID 788382 .
^ Х. Дж. Хаверкорт, Ф. ван Вальдервен, Четырехмерные кривые Гильберта для 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 .

Внешние ссылки [ править ]

[1] Д. Гильберт: О непрерывном отображении линии на поверхность. Математические анналы 38 (1891), 459–460.

[2] Г.Пеано: На кривой, заполняющей всю плоскую область. Mathematische Annalen 36 (1890), 157–160.

[3] Бурж, Паскаль. « Глава 1: Фракталы », Фракталы и хаос . Доступ: 9 февраля 2019 г.

[4] Мун, Б.; Джагадиш, Х.В.; Фалуцсос, К.; Сальц, Дж. Х. (2001), «Анализ свойств кластеризации кривой заполнения пространства Гильберта», IEEE Transactions on Knowledge and Data Engineering , 13 (1): 124–141, CiteSeerX 10.1.1.552.6697 , doi : 10.1109/ 69.908985 , S2CID 728511 .

[5] «Отображение всего Интернета с помощью кривых Гильберта» . blog.benjojo.co.uk . Проверено 02 января 2021 г.

[6] Спайрс, Шеннон В.; Голдсмит, Стивен Ю. (1998), Дрогул, Алексис; Тамбе, Милинд; Фукуда, Тосио (ред.), «Исчерпывающий географический поиск с помощью мобильных роботов по кривым, заполняющим пространство» , Collective Robotics , vol. 1456, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 1–12, doi : 10.1007/bfb0033369 , ISBN 978-3-540-64768-3 , получено 14 августа 2023 г.

[7] Садат, Сейед Аббас; Ваверла, Йенс; Воган, Ричард (2015). Фрактальные траектории для онлайн-неравномерного воздушного покрытия . Международная конференция IEEE по робототехнике и автоматизации (ICRA), 2015 г. стр. 2971–2976.

[8] Тиадмер Риемерсма (1 декабря 1998 г.). «Техника сбалансированного дизеринга» . Журнал пользователя C/C++ . Доктор Добб.

[9] И. Камель, К. Фалуцос, R-дерево Гильберта: улучшенное R-дерево с использованием фракталов, в: Материалы 20-й Международной конференции по очень большим базам данных, Morgan Kaufmann Publishers Inc., Сан-Франциско, Калифорния, США, 1994. , стр. 500–509.

[10] Ивис, Т.; Куэва, Д. (2007). «Архитектура сжатия гильбертового пространства для сред хранилищ данных». Хранилище данных и обнаружение знаний . Конспекты лекций по информатике. Том. 4654. стр. 1–12. дои : 10.1007/978-3-540-74553-2_1 . ISBN 978-3-540-74552-5 .

[11] Лемир, Дэниел; Касер, Оуэн (2011). «Переупорядочение столбцов для меньших индексов». Информационные науки . 181 (12): 2550–2570. arXiv : 0909.1346 . дои : 10.1016/j.ins.2011.02.002 . S2CID 15253857 .

[12] Программирование кривой Гильберта Джона Скиллинга

[13] Грант Теббин: Расчет координат кривой Гильберта

[14] Гамильтон, Швейцария; Рау-Чаплин, А. (2007). «Компактные индексы Гильберта: кривые, заполняющие пространство для областей с неравными длинами сторон». Письма об обработке информации . 105 (5): 155–163. дои : 10.1016/j.ipl.2007.08.034 .

[15] Альбер, Дж.; Нидермайер, Р. (2000). «О многомерных кривых со свойством Гильберта». Теория вычислительных систем . 33 (4): 295–312. CiteSeerX 10.1.1.7.2039 . дои : 10.1007/s002240010003 . S2CID 788382 .

[16] Х. Дж. Хаверкорт, Ф. ван Вальдервен, Четырехмерные кривые Гильберта для R-деревьев, в: Материалы одиннадцатого семинара по разработке алгоритмов и экспериментам, 2009, стр. 63–73.

[17] Вурхис, Дуглас: Кривые заполнения пространства и мера когерентности, стр. 26–30, Graphics Gems II.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

v т и Фракталы
Характеристики	Фрактальные измерения Ассуад Подсчет коробок Хигучи Корреляция Хаусдорф Упаковка Топологический Рекурсия Самоподобие
Итерированная функция система	Папоротник Барнсли Канторовский набор Снежинка Коха Моя губка Ковер Серпинского Треугольник Серпинского Аполлоническая прокладка Слово Фибоначчи Кривая заполнения пространства Кривая Бланманже Кривая Де Рама Минковский Кривая дракона Кривая Гильберта кривая Коха Кривая Леви C Кривая Мура Кривые Пеано Кривая Серпинского Кривая Z-порядка Нить Т-квадрат н-хлопья Фрактальные шутки шестихлопьевидный Кривая Госпера Дерево Пифагора Функция Вейерштрасса
Странный аттрактор	Мультифрактальная система
L-система	Фрактальный навес Кривая заполнения пространства H-дерево
Время побега фракталы	Фрактал горящего корабля Джулия сет Заполненный Ньютон фрактал Кролик Дуади Ляпунов фрактал Набор Мандельброта точка Мисюревича Набор Мультиброт Ньютон фрактал Треуголка Мандельбокс Мандельбулба
рендеринга Методы	Буддадброт Орбитальная ловушка Пиковерный стебель
Случайные фракталы	Броуновское движение Броуновское дерево Броуновский двигатель Фрактальный пейзаж полет Леви Теория перколяции Самоизбегающая прогулка
Люди	Майкл Барнсли Георг Кантор Билл Госпер Феликс Хаусдорф Десмонд Пол Генри Гастон Джулия Хельге фон Кох Пол Леви Aleksandr Lyapunov Бенуа Мандельброт Хамид Надери Йегане Льюис Фрай Ричардсон Вацлав Серпиньский
Другой	« Какова длина побережья Британии? » Парадокс береговой линии Фрактальное искусство Список фракталов по размерности Хаусдорфа Фрактальная геометрия природы (книга 1982 г.) Красота фракталов (книга 1986 г.) Хаос: создание новой науки (книга 1987 г.) Калейдоскоп Теория хаоса