Требуется помощь Попытка упростить этот алгоритм для сопоставления точек на произвольно большой 2d-плоскости с уникальными целыми числами

Question

Итак, как сказано в заголовке, мне нужна помощь в попытке сопоставить точки с 2-мерной плоскости с числовой линией таким образом, чтобы каждая точка была связана с уникальным положительным целым числом. Другими словами, мне нужна функция f:ZxZ->Z+, и мне нужно, чтобы f был инъективным. Кроме того, мне нужно бежать в разумные сроки.

Таким образом, я думал о том, чтобы просто подсчитывать точки, начиная с (1,1) и по спирали наружу.

Ниже я написал код Python, чтобы сделать это для некоторой точки (i, j)

      def plot_to_int(i,j):

a=max(i,j) #we want to find which "square" we are in
b=(a-1)^2 #we can start the count from the last square
J=abs(j)
I=abs(i)
if i>0 and j>0: #the first quadrant 
    #we start counting anticlockwise
    if I>J: 
        b+=J
    #we start from the edge and count up along j
    else:
        b+=J+(J-i)
    #when we turn the corner, we add to the count, increasing as i decreases
elif i<0 and j>0: #the second quadrant
    b+=2a-1 #the total count from the first quadrant
    if J>I:
        b+=I
    else:
        b+=I+(I-J)
elif i<0 and j<0: #the third quadrant
    b+=(2a-1)2 #the count from the first two quadrants
    if I>J:
        b+=J
    else:
        b+=J+(J-I)
else:
    b+=(2a-1)3
    if J>I:
        b+=I
    else:
        b+=I+(I-J)

return b

Я почти уверен, что это работает, но, как видите, это довольно громоздкая функция. Я пытаюсь придумать способ упростить эту логику «спирального счета». Или, возможно, есть другой метод подсчета, который проще кодировать, который тоже будет работать.

Answer 1

Вот полусырая идея:

1. Для каждой точки рассчитайте f = x + (y-y_min)/(y_max-y_min)
2. Найдите наименьшую дельту между любыми заданными f_n и f_{n+1}. Умножьте все значения на 1/d так что все значения разнесены по крайней мере на 1.
3. Возьми floor() из всех f значения.

Это похоже на проекцию на ось x, но она пытается распределить значения так, чтобы сохранить уникальность.

ОБНОВИТЬ:

Если вы не знаете всех данных и вам потребуется вводить новые данные в будущем, возможно, есть способ жестко закодировать произвольно большую или малую константу для y_max и y_min на шаге 1 и произвольная дельта dдля шага 2 в соответствии с границами ожидаемых значений данных. Или способ вычислить их значения в соответствии с ограничениями арифметики с плавающей запятой.