ℝ³ -> ℕ отображение для конечного числа значений

Question

Я ищу алгоритм, который способен отображать конечные, но большое количество трехмерных позиций (около 10^11) на индексы (поэтому отображение ³³ -> ℕ)

Я знаю, что это возможно и довольно просто сделать отображение ℕ -> ³³, и это по сути то, что я хочу сделать, но ℕ -> ³³ было бы непрактичным способом выяснить, какие индексы ℕ близки определенная позиция,

В идеале я также хотел бы гарантировать, что мое конечное подмножество ℕ не содержит дубликатов.

Некоторых советов о том, как это будет реализовано, чтобы дать более полное представление о трудностях и проблемах, с некоторым наивным решением этой проблемы:

Я пытаюсь придумать способ отображения звезд в галактике уникальный идентификатор, который затем я могу использовать в качестве «семени» для генератора случайных чисел, отображение ℕ -> ³³ потребовало бы, чтобы я перебирал все ℕ, чтобы найти значения ℝ³, которые находятся вблизи данного места, что, очевидно, не практический подход

Я уже нашел некоторую информацию о функции спаривания канторов и огибающей, но это вызывает проблемы, поскольку они в основном относятся к ℕⁿ, а не ℝⁿ.

Не забудьте, что мои значения ℝ³ соответствуют сетке, если бы они могли отображать ³³-> ³³, выяснив, в каком «поле» находится значение, а затем используйте функцию спаривания кантора, чтобы выяснить, к какому ℕ принадлежит в этом поле, но в моих ситуациях ящик может содержать несколько значений или ни один.

Заранее спасибо за любую помощь

Answer 1

Вы можете использовать k-d tree пространственно разметить множество точек. Чтобы отобразить на натуральное число, трактуйте путь через дерево к каждой точке как строку двоичных цифр, где 0 - левая ветвь, а 1 - это правильная ветвь. Это может не дать вам именно то, что вы ищете, поскольку некоторые точки, которые пространственно близки друг к другу, могут лежать на разных ветвях и, следовательно, численно далеки друг от друга. Однако, если две точки близки друг к другу численно, они будут близки друг к другу пространственно.

В качестве альтернативы вы также можете использовать octree, и в этом случае вы получаете по три бита за каждый уровень, который вы спускаете в дерево. Вы можете полностью разделить пространство, чтобы каждый регион содержал не более одной точки интереса.