Комментарии 9
Знакомая картина — это 3-мерный симплекс кривой Гильберта!
Вот отсюда стало непонятно.
Что такое симплекс?
Что такое трехмерный симплекс?
Что такое симплекс кривой?
В свое время нашел неожиданное для себя применение коду Грэя при создании варианта пространственного индекса: infostart.ru/public/551583. Спасибо за статью — она пояснила мне полученный тогда эффект с новой стороны. Еще про октадеревья нужно будет подумать.
Z-кривая, кстати, ещё называется Кривой Мортона. Полезная вещь при работе с вокселями в 3d.
Впервые познакомившись с кодом Грея (он используется в схемотехнике при переходе из одного тактируемого домена в другой), я задумался о том, почему он вообще существует. И был очень рад найти изящное геометрическое доказательство. Оно по смыслу практически совпадает с тем, что приводится в этой статье и в других источниках. Только я не пытался отобразить это в кривую Гильберта, а рисовал обычный гиперкуб нужной размерности и ломаную на его ребрах.
Я использую следующее определение. Код Грея — это такое биективное отображение g: {0,1}^n -> {0,1}^n, что g(x) и g(x+1) отличаются ровно в одном разряде. При этом обычно под операцией + подразумевают обычное сложение двоичных чисел, однако я предлагаю немного обобщить и считать, что сложение делается по модулю 2^n. Тогда точки 00…0 и 11…1 оказываются соседними, и их образы тоже должны отличаться ровно в одном разряде. Разница с классическим определением заключается в том, что соответствующая кривая в геометрическом представлении оказывается замкнутой. Теперь можно применить индуктивное построение из этой статьи, слегка модифицировав его. Возьмем замкнутую кривую размерности n, выберем на ней произвольный отрезок AB удалим его. Полученную (незамкнутую) кривую скопируем в еще одну такую же (пусть при этом точки A и B перешли в A' и B' соответственно) и полученные экземпляры кривой поместим на противоположные грани гиперкуба размерности (n+1). Теперь осталось добавить отрезки AA' и BB', чтобы получилась новая замкнутая кривая размерности (n+1) с теми же свойствами. (В качестве базы индукции можно взять n=2 (это квадрат), но и для n=1 тоже будет работать, только вместо отрезка 0—1 нужно взять цикл 0—1—0, состоящий из двух одинаковых отрезков.) Если каждый раз в качестве A и B выбирать точки 00…0 и 11…1, то получится в точности «миссионерский» вариант из статьи или, что то же самое, код Грея, полученный по алгоритму из Википедии.
Я использую следующее определение. Код Грея — это такое биективное отображение g: {0,1}^n -> {0,1}^n, что g(x) и g(x+1) отличаются ровно в одном разряде. При этом обычно под операцией + подразумевают обычное сложение двоичных чисел, однако я предлагаю немного обобщить и считать, что сложение делается по модулю 2^n. Тогда точки 00…0 и 11…1 оказываются соседними, и их образы тоже должны отличаться ровно в одном разряде. Разница с классическим определением заключается в том, что соответствующая кривая в геометрическом представлении оказывается замкнутой. Теперь можно применить индуктивное построение из этой статьи, слегка модифицировав его. Возьмем замкнутую кривую размерности n, выберем на ней произвольный отрезок AB удалим его. Полученную (незамкнутую) кривую скопируем в еще одну такую же (пусть при этом точки A и B перешли в A' и B' соответственно) и полученные экземпляры кривой поместим на противоположные грани гиперкуба размерности (n+1). Теперь осталось добавить отрезки AA' и BB', чтобы получилась новая замкнутая кривая размерности (n+1) с теми же свойствами. (В качестве базы индукции можно взять n=2 (это квадрат), но и для n=1 тоже будет работать, только вместо отрезка 0—1 нужно взять цикл 0—1—0, состоящий из двух одинаковых отрезков.) Если каждый раз в качестве A и B выбирать точки 00…0 и 11…1, то получится в точности «миссионерский» вариант из статьи или, что то же самое, код Грея, полученный по алгоритму из Википедии.
Впервые познакомившись с кодом Грея (он используется в схемотехнике при переходе из одного тактируемого домена в другой), я задумался о том, почему он вообще существует
Фишка кода Грея, что при каждом шаге меняется только один бит. В результате нет переходного состояния, как когда часть элементов уже переключилась, а часть ещё нет.
zzeng вы самоподобны!
-RE Забавно, что в этом случае преобразование пройденного от начала координат пути в код, который может быть разобран на разряды-координаты тривиально.
НЛО — это стеб
-RE Забавно, что в этом случае преобразование пройденного от начала координат пути в код, который может быть разобран на разряды-координаты тривиально.
НЛО — это стеб
Ага. Получается что любой обход графа можно рассматривать как движение по ребрам кубической гиперрешётки с размерностью равной (или большей) максимальному количеству ребер исходящих из узла.
Интересная метрика для графа получается.
Буду думать.
Вопрос к знатокам это свойство где-нибудь используется?
Вот, например
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Про геометрический смысл кодов Грея