Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 8
Комментарии про Кащея всегда побеждают… Вспомнился такой перл про визуализацию бизнес-данных:
«Никого уже не удивишь технологией drill-down, изобретателем которой по праву можно считать знаменитого русского просветителя и общественного деятеля Кощея Бессмертного (смерть на конце иголки, иголка в яйце, яйцо в утке, утка в зайце, заяц в сундуке, бла-бла)» за авторством eugenebartosh
Статья, кстати, гуд)
«Никого уже не удивишь технологией drill-down, изобретателем которой по праву можно считать знаменитого русского просветителя и общественного деятеля Кощея Бессмертного (смерть на конце иголки, иголка в яйце, яйцо в утке, утка в зайце, заяц в сундуке, бла-бла)» за авторством eugenebartosh
Статья, кстати, гуд)
а потом сохраняем ее в кодах Грея(два бита на одно деление)
А это как и зачем?
Посмотрите на картинку в конце статьи — это деление ноды на 4 части.
Выбор ноды по Х — это 0 и 1, выбор ноды по Y — это 0 и 1.
Итого ноды идут как 00-01-10-11, или 0-1-2-3. Это одновременно и Z код, и 2-битный код Грея.
Есть варианты «делений» сразу через «несколько уровней», когда на выбор идет сразу через 8-16 нод. Например монга любит сразу на пару уровней Hilber вешать, так как его считать сложно.
И это уже не Грей будет.
Выбор ноды по Х — это 0 и 1, выбор ноды по Y — это 0 и 1.
Итого ноды идут как 00-01-10-11, или 0-1-2-3. Это одновременно и Z код, и 2-битный код Грея.
Есть варианты «делений» сразу через «несколько уровней», когда на выбор идет сразу через 8-16 нод. Например монга любит сразу на пару уровней Hilber вешать, так как его считать сложно.
И это уже не Грей будет.
А разве код Грея это не 0-1-3-2? Собственно, вопрос в том, есть ли у кривой Пеано преимущество перед Z-кривой, или там только проблемы с выбором сегментов, пересекающих анализируемую окрестность точки.
Это уже вопрос из момента сохранения локальности данных и области использования, точнее нужных областей выборки.
Пеано — это вообще «родоначальник» space filling curve, но эта трансформация обладает самым большим «расстоянием».
Примерно так
На самом деле в (русской) википедии написано что Hilbert это тоже пеано, но в общем — en.wikipedia.org/wiki/Space-filling_curve
У Z есть только одно, но очень крутое, преимущество — полная симметрия и очень простое вычисление как «туда» так и «обратно».
Пеано — это вообще «родоначальник» space filling curve, но эта трансформация обладает самым большим «расстоянием».
Примерно так
Два значения в Hilbert находятся очень близко друг от друга в 2д эвклидовом пространстве(те исходном)
Два значения в Morton находятся близко — из-за перекладины в Z вся статистика насмарку.
Два значения в Пеано находятся не далеко.
На самом деле в (русской) википедии написано что Hilbert это тоже пеано, но в общем — en.wikipedia.org/wiki/Space-filling_curve
У Z есть только одно, но очень крутое, преимущество — полная симметрия и очень простое вычисление как «туда» так и «обратно».
Самый большой вопрос: всегда ли рядом находящиеся точки получают близкие коды квадратиков?
Посмотрите, например, на Пиренеи — часть находится в квадратике 031, а часть в 122, что как бы очень далеко по индексу. Нужен как-то более умный обход квадратов, чем просто Z-кривая.
Посмотрите, например, на Пиренеи — часть находится в квадратике 031, а часть в 122, что как бы очень далеко по индексу. Нужен как-то более умный обход квадратов, чем просто Z-кривая.
Любая кривая рекурсивного разбиения будет иметь такую проблему. От конкретной нумерации разбиения квадродерева зависит только некое численное выражение «дальности».
Одна половина Лондона, от второй всегда будет «далеко», так как по этому место проходит первый уровень разбиния.
Но кроме Z(и вообще quad) кодов есть еще, например, кривая Серпинского, в основе которой лежит разбиение треугольниками. В ней «далеко» будет в других местах.
Еще кодирование разбиения в кодах грея — в численном эквиваленте два соседних значениях могут быть далеко, но различаться при этом будут всего на 1 бит(2 по диагонали). И даже нормальная метрика под это дело есть — расстояние Хэминга.
Простейшие коды 2Д Грея работают просто — переводим X,Y в gray (x ^ x>>1), после чего делаем bitInterlaving и получаем Z код, основанный на кодах грея…
Одна половина Лондона, от второй всегда будет «далеко», так как по этому место проходит первый уровень разбиния.
Но кроме Z(и вообще quad) кодов есть еще, например, кривая Серпинского, в основе которой лежит разбиение треугольниками. В ней «далеко» будет в других местах.
Еще кодирование разбиения в кодах грея — в численном эквиваленте два соседних значениях могут быть далеко, но различаться при этом будут всего на 1 бит(2 по диагонали). И даже нормальная метрика под это дело есть — расстояние Хэминга.
Простейшие коды 2Д Грея работают просто — переводим X,Y в gray (x ^ x>>1), после чего делаем bitInterlaving и получаем Z код, основанный на кодах грея…
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Где смерть Кащеева?