Кривая Гильберта: заполняющая пространство кривая

Введение

Кривая, заполняющая пространство

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

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

И истинная кривая Гильберта, и ее дискретные приближения полезны, поскольку они обеспечивают отображение между одномерным и двумерным пространством, достаточно хорошо сохраняющее локальность. Это означает, что две точки данных, близкие друг к другу в одномерном пространстве, останутся близкими и после преобразования. Обратное, однако, не всегда верно. Благодаря этому свойству локальности кривая Гильберта широко используется в информатике. Например, диапазон IP-адресов, используемых компьютерами, можно отобразить на изображение с помощью кривой Гильберта. Код для генерации изображения будет преобразовывать координаты из двумерных в одномерные для определения цвета каждого пикселя, и кривая Гильберта иногда используется, поскольку она располагает близкие IP-адреса рядом друг с другом на изображении. Свойство локальности кривой Гильберта также применялось при разработке алгоритмов для исследования местности мобильными роботами. В алгоритме, известном как дитеринг Римерсмы, фотографии в оттенках серого можно преобразовать в дитерированное черно-белое изображение с использованием пороговой обработки, при этом остаток от каждого пикселя добавляется к следующему пикселю вдоль кривой Гильберта. Код для этого будет преобразовывать координаты из одномерных в двумерные, и кривая Гильберта иногда используется, поскольку она не создает отвлекающих узоров, которые были бы заметны глазу, если бы порядок следования пикселей был просто слева направо в каждой строке. Кривые Гильберта в более высоких измерениях являются обобщением кодов Грея и иногда используются для аналогичных целей по тем же причинам. Для многомерных баз данных предлагается использовать порядок Гильберта вместо порядка Z, поскольку он лучше сохраняет локальность. Например, кривые Гильберта использовались для сжатия и ускорения индексов R-деревьев (см. Гильбертово R-дерево). Они также применялись для сжатия хранилищ данных. Линейное расстояние любой точки вдоль кривой можно преобразовать в координаты в n измерениях для заданного n, и наоборот, используя один из нескольких стандартных математических методов, таких как метод Скиллинга. Кривые Гильберта можно эффективно реализовать даже в том случае, если пространство данных не является квадратным. Кроме того, существует несколько возможных обобщений кривых Гильберта для более высоких измерений.

Both the true Hilbert curve and its discrete approximations are useful because they give a mapping between 1D and 2D space that preserves locality fairly well. This means that two data points which are close to each other in one dimensional space are also close to each other after folding. The converse cannot always be true. Because of this locality property, the Hilbert curve is widely used in computer science. For example, the range of IP addresses used by computers can be mapped into a picture using the Hilbert curve. Code to generate the image would map from 2D to 1D to find the color of each pixel, and the Hilbert curve is sometimes used because it keeps nearby IP addresses close to each other in the picture. The locality property of the Hilbert curve has also been used to design algorithms for exploring regions with mobile robots. In an algorithm called Riemersma dithering, grayscale photographs can be converted to a dithered black and white image using thresholding, with the leftover amount from each pixel added to the next pixel along the Hilbert curve. Code to do this would map from 1D to 2D, and the Hilbert curve is sometimes used because it does not create the distracting patterns that would be visible to the eye if the order were simply left to right across each row of pixels. Hilbert curves in higher dimensions are an instance of a generalization of Gray codes, and are sometimes used for similar purposes, for similar reasons. For multidimensional databases, Hilbert order has been proposed to be used instead of Z order because it has better locality preserving behavior. For example, Hilbert curves have been used to compress and accelerate R tree indexes (see Hilbert R tree). They have also been used to help compress data warehouses. The linear distance of any point along the curve can be converted to coordinates in n dimensions for a given n, and vice versa, using any of several standard mathematical techniques such as Skilling's method. It is possible to implement Hilbert curves efficiently even when the data space does not form a square. Moreover, there are several possible generalizations of Hilbert curves to higher dimensions.

Другие варианты реализации

В книге Graphics Gems II обсуждается когерентность кривой Гильберта и приводится её реализация. Кривая Гильберта широко используется при рендеринге изображений и видео. Популярные программы, такие как Blender и Cinema 4D, используют кривую Гильберта для трассировки объектов и рендеринга сцен. Программное обеспечение для нарезки, используемое для преобразования 3D-моделей в траектории инструмента для 3D-принтера, обычно предлагает кривую Гильберта в качестве варианта для схемы заполнения.