Как определить ближайшие точки на плоскости путем хеширования?
Все читаю статьи на википедии и хабре и до конца не помогу понять суть методов хеширования.
Находил вот такие выражения ((x * 73856093 + y * 19349669 + z * 83492791))% n( и подобные) , но как не пытаюсь их проверить, то не как не выходит. Хотя я да же не понимаю что должно выйти, и как мне работать с этим хешом.
Знаю хеш-множества, что-то проецирую и в чем-то не стыковки выползают в моем представлении.
К примеру в хеш-множестве, мне не важен хеш и где-там обьект в этом массиве располагается, функция сама найдет и дело с концом.
Алексей Тен, вот например https://habr.com/post/182998/
тут вот такая картинка есть, с шариками, и то как в одномерный массив их запихивают,
и к примеру если бы вставить шарик в клетку "5", то он будет очень близок к шарику в
в клетки "1", но в последующем хешировании в массив, он будет в середине, и ни как не похоже на то что будет близок к шарику "1".
Даниил, смысл такой: вы хотите добавить шарик в клетку 5 и вам надо выяснить с какими шариками он может пересечься. Вы берёте хеши клеток 1, 2, 6, 9 и 10 (соседних с клеткой 5) и смотрите в таблице какие шарики там есть. Их немного и вы просто перебором сравниваете расстояния до нового шарика. А шарики которые в других клетках даже не рассматриваете, они точно гарантированно далеко
Алексей Тен, вы предложили очевидное решение по конкретно этому рисунку, а меня интересует конкретно 2 картинка, и из нее не как не следует что в клетке 5 надо проверять 1,2,6,10
Кажется вам нужно ещё раз прочитать статью.
Вторая таблица это хеш. Мы в пространстве находим какие ячейки хеша надо проверить, а из хеша быстро достаём только нужные объекты
Вообще-то в приведенной статье приведена несколько другая формула. (Floor(pos.x / cellSize) * 73856093) ^ (Floor(pos.y / cellSize) * 19349663) ^ (Floor(pos.z / cellSize) * 83492791)
Вы не находите, что операция "^" несколько отличается от операции "+"?
я знаю, скопировал первую формулу что гугл вернул, но что дальше делать я не понимаю.
Почему-то в статьях умалчивают что дальше, как определить ближайшие точки.
вот у меня точка (1,1,1) и есть точка (1,1,2), есть точка (1,2,100) и она очень далеко, и для всех трех точек я получу разное значение, и что дальше, вообще не понимаю.