Хеширование 2D, 3D и nD векторов

Что такое хорошие хэширующие функции (быстрое, хорошее распределение, несколько столкновений) для хеширования 2d и 3d векторов, состоящих из плавающих IEEE 32 бит. Я предполагаю общие 3d-векторы, но также приветствуются алгоритмы, предполагающие нормали (всегда в [-1,1]). Я также не боюсь манипуляции с битами, так как поплавки IEEE также являются обычными платами IEEE.

Еще одна общая проблема заключается в хешировании Nd float-vector, где N довольно мало (3-12) и постоянна, но неизвестна во время компиляции. В настоящий момент я просто беру эти поплавки как uints и XOR их вместе, что, вероятно, не лучшее решение.

Ответ 1

Существует пространственная хеш-функция, описанная в Оптимизированное пространственное хеширование для обнаружения столкновений деформируемых объектов. Они используют хеш-функцию

hash (x, y, z) = (x p1 xor y p2 xor z p3) mod n

где p1, p2, p3 большие простые числа, в нашем случае 73856093, 19349663, 83492791, соответственно. Значение n - это размер хеш-таблицы.

В статье x, y и z - дискретизированные координаты; вы могли бы также использовать двоичные значения ваших поплавков.

Ответ 2

У меня есть два предложения.

Предположим ячейку сетки размера l и квантуем координаты x, y и z, вычислив ix = floor (x/l), iy = floor (y/l) и iz = floor (z/l), где ix, iy и iz - целые числа. Теперь используйте хэш-функцию, определенную в Оптимизированное пространственное хеширование для обнаружения столкновений деформируемых объектов

Если вы не выполняете квантование, оно не будет чувствительно к близости (локальность).

Чувствительность локализации была упомянута для хэширования векторов с большими размерами. Почему бы им не использовать их для векторов 3d или 2d? Вариант LSH с использованием адаптивной для евклидовой дистанционной метрики (которая является тем, что нам нужна для 2d и 3d векторов) называется локальным чувствительным хешированием с использованием p-устойчивых распределений. Очень читаемый учебник здесь.