Уроки, алгоритмы, программы, примеры

Вход на сайт

Материалы по разделам

Построения
на плоскости (2D)
Графика
в пространстве (3D)
Вычислительная
геометрия
Физическое
моделирование
Фрактальная
графика

Новые комментарии

torrvic, возможно, Вам нужно добавить -lGLU
Извините за тупой вопрос. У меня при сборке Вашего примера выходит ошибка: "undefined reference to gluLookAt". Не могу найти в какой библиотеке находится эта функция. У меня задано: -lGL -lglut ... Искал в /usr/lib таким образом: nm lib*so* | grep...
Здравствуйте. Спасибо за проект. У меня вопрос, по какой причине определение принадлежности точки многоугольнику работает некорректно, если координаты из больших чисел состоят, например: int[] vertex = new int[] {...
Сейчас проверила нашла причину не запускания // Создание контекста воспроизведения OpenGL и привязка его к панели на форме OpenGLControl1:=TOpenGLControl.Create(Self); with OpenGLControl1 do begin Name:='OpenGLControl1'; //вот тут...
Ну..кажется что то пошло не так http://pp.usera...

Счетчики и рейтинг

Рейтинг@Mail.ru

Кривые Гильберта впервые были описаны в 1891 году немецким математиком Давидом Гильбертом.

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

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

Не разрешается, чтобы веревка пересекала сама себя.

Есть много способов сделать это, однако кривые Гильберта имеют некоторые дополнительные интересные свойства. Чтобы понять эти свойства, мы должны внимательнее посмотреть на то, как они строятся рекурсивно.

Рекурсия

Основным элементом кривой Гильберта является П-образный элемент.

Здесь у нас квадратная сетка 2x2. Начнем с левого верхнего угла и проведем веревку через другие три квадрата сетки, закончив в правом верхнем углу.

Теперь представьте, что мы удваиваем размер сетки, получая сетку 4x4.

Мы можем представить эту сетку 4x4 в виде набора 4 = 2x2 сеток, каждая из которых имеет размер 2x2 (как набор матрешек).

Мы хотим пересечь сетку более высокого уровня в таком порядке 0->1->2->3 (это показано большими желтыми стрелками), а затем внутри этой сетки используем все тот же П-образный шаблон обхода для каждой из сеток меньшего уровня.

Эта запутанная и извилистая кривая проходит через каждый квадрат сетки.
Если вы вернетесь назад, к кривой на сетке , приведенной выше, то увидите, что она построена из кривых для четырех сеток , размещенных по П-образному образцу…

Вот некоторые кривые Гильберта по возрастанию порядка:

От 1D к 2D

Здесь все становится немного интереснее. Вместо того чтобы использовать веревку, представим, что мы по сетке располагаем измерительную ленту.

Поскольку лента извивается и разворачивается в противоположном направлении вокруг сетки, получается интересное свойство. Если сопоставить расстоянию d , отмеренному лентой, пару координат (x,y) точек на исходной сетке, то получится, что другие отметки на ленте (близкие к d) соответствуют координатам, близким к (x,y).

Мы получили полезную функцию перехода от размерности 1 к двум измерениям, она сохраняет свойство локальности (примеч. Проекция, сохраняющая свойство локальности — линейное проективное отображение, которое оптимально сохраняет структуру окрестности точки из области определения).

Близкие значения d соответствуют близким значениям .

Замечание. Обратное не всегда верно (что неизбежно при отображении двух измерений на одно измерение). Обязательно будут случаи, когда точки с геометрически близкими координатами (x,y) будут соответствовать сильно отличающимся значениям на ленте d. Тем не менее, за исключением этих случаев, кривые Гильберта также неплохо работают и на обратных отображениях.

Ниже можно увидеть квадрат, раскрашенный с использованием кривой Гильберта. Цвета, близкие друг к другу на спектре, имеют близкие координаты (x,y).

(Близкие координаты (x,y) не всегда соответствуют близким цветовым оттенкам цвета по причине, описанной выше, хотя часто это так. Отсутствие непрерывности наиболее заметно вдоль двух границ. Некоторые интересные обходы этого ограничения были придуманы, больше об этом — позже).

Более высокие размерности

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

Вариант трехмерной кривой показан слева. В этом случае точки на кривой, численно близкие друг к другу, также близки в трехмерном пространстве.

Легко увидеть, как это может быть распространено на более высокие измерения.

Практическое применение

Функции Гильберта могут помочь в индексировании пространственных баз данных; при поиске записи, близкой по географическому положению они дают возможность определить приоритет для поиска.

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

В более высоких размерностях они могут быть использованы для планирования задач в компьютерных программах с параллельной обработкой данных, преобразования многомерного распределения задач в одномерное и привязки близких задач к точкам размещения с более высоким уровнем близости.

Исследования

Ранее уже говорилось, что не все в кривых Гильберта идеально. (Точки с близкими значениями d имеют схожие значения (x,y), но обратное не всегда верно).

Это свойство было бы невероятно полезно, например, при осуществлении эффективного доступа к данным. Давайте представим, что у вас есть некоторые данные, хранящиеся в цифровом виде (точки их размещения с очень большим временем доступа), и требуется их индексация и доступ к ним эффективным образом, что нужно сделать географически. Как известно, преобразование координат (x,y) в значения d не может гарантировать, что близкие значения d расположены в непосредственной близости. Большую часть времени да, но время от времени нет.

Чтобы избежать этого, вместо простого индексирования данных на одной кривой Гильберта, данные переводятся на множество гильбертовых кривых (как правило, полученных вращением и горизонтальными/вертикальными сдвигами одной кривой).