Как рассчитать относительные векторы из списка точек, от одной точки к каждой другой точке

Question

У меня есть список точек в парах (x,y), который представляет позиции списка агентов.Например, учитывая 3 агента, есть 3 пары точек, которые я храню следующим образом:

points = np.array([[x1, y1],
                   [x2, y2],
                   [x3, y3]])

Я хотел бы рассчитать последующий массив, то есть относительную позицию от одного агента к каждому другому агенту., но НЕ сам по себе.Итак, используя приведенные выше данные, я бы хотел сгенерировать массив relative_positions, используя массив points.points может иметь N позиций (я могу иметь до 50-100 агентов одновременно).

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

relative_positions = [[x2-x1, y2-y1],
                      [x3-x1, y3-y1],
                      [x1-x2, y1-y2],
                      [x3-x2, y3-y2],
                      [x1-x3, y1-y3],
                      [x2-x3, y2-y3]]

Например, учитывая четыре позиции агента, хранящиеся в виде массива с нулевыми значениями:

agent_points = np.array([[10, 1],
                         [30, 3],
                         [25, 10],
                         [5, 5]])

Я хотел бы сгенерировать вывод:

relative_positions = [[30-10,  3-1],
                      [25-10, 10-1],
                      [5-10,   5-1],
                      [10-30,  1-3],
                      [25-30, 10-3],
                      [5-30,   5-3],
                      [10-25, 1-10],
                      [30-25, 3-10],
                      [5-25,  5-10],
                      [10-5,   1-5],
                      [30-5,   3-5],
                      [25-5,  10-5]]

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

Answer 1

Подход № 1

С a входным массивом вы можете сделать -

d = (a-a[:,None,:])
valid_mask = ~np.eye(len(a),dtype=bool)
out = d[valid_mask]

По сути, мы расширяем a до 3D такой, что первая ось сделана outer-broadcastable, а затем мы выполняем вычитание против его 2D версии, в результате чего получается mxmx2 -образный вывод, с m, являющимся a.shape[0].Схематически обозначено -

a[:, None, :]    :  4 x 1 x 2
a                :      4 x 2
output           :  4 x 4 x 2

More info.

Еще один способ создания valid_mask, будет -

r = np.arange(len(a))
valid_mask = r[:,None] != r

Подход № 2

Мы используем np.lib.stride_tricks.as_strided, чтобы получить недиагональную маску для массивов 3D (вдоль первых двух осей), так что мы будем использовать ее здесь для маскировки массива различийd.Генерация этой маски основана на проблеме массива 2D, которая была опубликована here, а для случая 3D это выглядело бы примерно так:

def nodiag_view3D(a):
    m = a.shape[0]
    p,q,r = a.strides
    return np.lib.stride_tricks.as_strided(a[:,1:], shape=(m-1,m,2), strides=(p+q,q,r))

Чтобы решить нашу проблему, было бы -

d = (a-a[:,None,:])
out = nodiag_view3D(d).reshape(-1,a.shape[1])

---

Сроки, чтобы продемонстрировать, как подход № 2 улучшается на # 1

In [96]: a = np.random.rand(5000,2)

In [97]: d = (a-a[:,None,:])

In [98]: %%timeit
    ...: valid_mask = ~np.eye(len(a),dtype=bool)
    ...: out = d[valid_mask]
1 loop, best of 3: 763 ms per loop

In [99]: %%timeit
    ...: r = np.arange(len(a))
    ...: valid_mask = r[:,None] != r
    ...: out = d[valid_mask]
1 loop, best of 3: 767 ms per loop

In [100]: %timeit nodiag_view3D(d).reshape(-1,a.shape[1])
10 loops, best of 3: 177 ms per loop

Answer 2

Хотя у меня нет ничего конкретного решения (я уверен, что оно существует), двойная проверка цикла и проверка идентификатора могут сделать свое дело просто отлично. Однако, если points вырастет, потребуется некоторое время.

points = [
    [x1, y1],
    [x2, y2],
    [x3, y3]
]

relative_positions = []
for point1 in points:
    for point2 in point:
        if id(point1) != id(point2):
            relative_positions.append([CALC_HERE_OR_FUNCTION])