Новости

Как правильно применять в JavaScript асинхронные функции: примеры работы с ES 2017
От автора: возможность писать на JavaScript асинхронные функции является важным обновлением в ES2017. Что такое асинхронные функции? Асинхронные функции — это функции, которые возвращают promise. Мы

WordPress JavaScript — как правильно подключить файл скрипта к шаблону сайта
Использование в шаблонах WordPress JavaScript скриптов давно стало обычным делом. Их подключение возможно несколькими способами, начиная с классического варианта с использование голого HTML. Но чтобы все

Как исправить JavaScript error "ВКонтакте"? Что делать при ошибках JavaScript в "ВКонтакте"?
"ВКонтакте" - это на сегодняшний день самый удобный русскоязычный ресурс, который является не только популярнейшей социальной сетью, но и сервисом для прослушивания аудиозаписей и просмотра видео. Здесь

Правильное использование Tor Browser
Tor Browser полностью анонимен – Миф или реальность? Многие считают, что Tor — это полностью анонимное и безопасное средство для интернет-серфинга, которое не дает никому возможность контролировать то,

Javascript error object is not a function вконтакте как исправить
"ВКонтакте" - это на сегодняшний день самый удобный русскоязычный ресурс, который является не только популярнейшей социальной сетью, но и сервисом для прослушивания аудиозаписей и просмотра видео. Здесь

Как исправить ошибку javascript error вконтакте
На сегодняшний день «Вконтакте» является наиболее удобным русскоязычным ресурсом, который представляет собой не только крупнейшую социальной сеть, но и сервис для просмотра видео и прослушивания аудиозаписей.

Что такое JavaScript и для чего он используется?
Подробности декабря 10, 2015 Просмотров: 20225 В интернете миллионы веб-страниц,

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

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

Рекомендации решившим начать изучать JavaScript
Если вы решили начать изучать JavaScript , то эта статья для вас. Надеюсь, что её прочтение избавит вас в будущем от множества ошибок и сделает его изучения более простым, быстрым и эффективным. В статье

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

Опубликовано: 01.09.2018

видео Кривые Гильберта

Аксиоматическая теория Гильберта исчисления высказываний

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



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


Топология: Теорема Жордана

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


И. Лосев - Схемы Гильберта и комбинаторика I

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

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

Рекурсия

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

Здесь у нас квадратная сетка 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 расположены в непосредственной близости. Большую часть времени да, но время от времени нет.

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

rss