Как эффективно рассчитать расстояние в тороидальном пространстве?

Question

У меня есть игровое окно размером 640 на 480, и оно заполнено частицами, но когда частица уходит в одну сторону, она переходит в другую (т. Е. Это тороид).

IЯ хочу рассчитать расстояние между каждой частицей, так как это будет использоваться для приложения различных сил к каждой частице.

Сначала я перебрал каждую пару частиц, а затем перемасштабировал все так, чтобы первая частица в паре былапо центру, а затем рассчитал расстояние до второй частицы, но это было очень медленно для запуска.

Затем я нашел некоторые функции в scipy.spatial.distance, которые позволяют мне очень быстро вычислить расстояние между всеми точками, ноединственная проблема заключается в том, что он не учитывает обтекание.

Вот мой текущий код

from scipy.spatial.distance import pdist, squareform
...
distance = squareform(pdist([(p.x, p.y) for p in particles]))

Это работает для частиц вблизи центра, но если одна частица находится в(1, 320), а другая частица находится в (639, 320), то она рассчитывает их расстояние как 638 вместо 2. Это не учитываетучитывайте перенос.

Есть ли другая функция, которую я могу использовать, или какое-то преобразование, которое я могу применить до / после, чтобы принять во внимание перенос?

Answer 1

Вы можете вычислить наименьшую из разностей x и y (разница в окне относительно расстояния пересечения края) следующим образом:

game_width = 640
game_height = 480

def smaller_xy(point1, point2):

    xdiff = abs(point1.x - point2.x)
    if xdiff > (game_width / 2):
        xdiff = game_width - xdiff

    ydiff = abs(point1.y - point2.y)
    if ydiff > (game_height / 2):
        ydiff = game_height - ydiff

    return xdiff, ydiff

То есть, если расстояние в окне вx или y направления больше, чем половина размера окна в этом направлении, лучше отойти от края - и в этом случае расстояние будет размером окна в этом направлении минус исходное расстояние в окне.

Очевидно, что после разделения x и y вы можете вычислить расстояние между точками следующим образом:

import math

small_x, small_y = smaller_xy(p1, p2)
least_distance = math.sqrt(small_x**2 + small_y**2)

Однако, в зависимости от того, как определен ваш расчет силы, вы можете обнаружить, что всена самом деле нужен квадрат расстояния (просто (small_x**2 + small_y**2)), и поэтому вы можете избежать работы по поиску sqrt.

Чтобы перевести это значение в scipy.pdist, обратите внимание, что pdistможет вызываться с аргументом функции в дополнение к точкам, как:

Y = pdist(X, func)

Это последняя форма вызова, показанная в описании pdist в https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.pdist.html#scipy.spatial.distance.pdist

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

Answer 2

Представим, что вы копируете четыре доски сверху, снизу, слева и справа на исходную доску, а также частицы с оригинальной доски на новые платы.Давайте также отметим частицы.

Обозначим N частицы на исходной доске o(i), i, начиная с 1 и N.a(i) для частиц на реплицированной доске выше.b(i), l(i), r(i) для нижнего, левого и правого соответственно.

Для всех различных i и j вам необходимо найти расстояния между o(i) и o(j), o(i) и a(j) и т. Д. И т. Д. Для каждой пары i и j рассчитывается расстояние 5x5 = 25.Когда у вас есть все эти расстояния, возьмите минимум для каждой пары, это ваше расстояние для i и j.

Я думал, что могут быть способы обрезать вычисления.Но я думаю, вам нужно как минимум рассчитать расстояния между частицами до границ и сравнить их с расстояниями на оригинальной доске.Это тоже накладные расходы.