Как эффективно сравнить два набора неупорядоченных векторов (`np.ndarray`)?

Question

Я пытался прояснить свой вопрос. Старое отступление все еще можно найти в конце этого.

ПРОБЛЕМА : у меня есть n на 3 матрицы A (np.ndarray) n точек в три измерения. Мы говорим, что эти точки симметричны c относительно преобразования R (матрица 3 на 3), если они неподвижны как неупорядоченное множество.

Это означает, что A и A @ R.T отличаются на 1. самое большее перестановка и 2. после исправления перестановки обе матрицы могут отличаться числовым параметром допуска: np.allclose(A, permuted(A @ R.T)) == True (заранее я не знаю permuted(), и это, безусловно, зависит от R).

ВОПРОС : как мне создать следующую функцию:

def is_symmetric(A, R, atol=1e-5) -> bool:
    # checks symmetry as defined above, considering both numerical noise
    # and permutation of vectors.

(Некоторое обсуждение возможных путей и моих сомнений и попыток можно найти ниже.)

---

OLD DIGRESSION :

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

import numpy as np
R = np.array([[0, -1, 0],  # 90° rotation around z as an example
              [1,  0, 0],
              [0,  0, 1]])

Дело в том, что Я принимаю перестановку векторов : пока какая-то начальная позиция преобразуется в другую, ранее существовавшую локацию, я в порядке. Это означает проверку преобразованных пар векторов от одного к другому.

Наивное решение будет зацикливаться на строках A @ R.T (где A - матрица, строки которой положения точек) и попытайтесь сопоставить преобразованный вектор для каждой начальной строки A, который, по-видимому, растет квадратично с числом столбцов.

Другой возможностью будет предварительное упорядочение векторов ( скажем, по значениям их координат):

A = np.array([[1,   0,   0],  # some points
              [0,   1,   0],
              [0,   0,   1],
              [0.5, 0.5, 0]])
A = np.array(sorted(A, key=lambda v: (v[2], v[1], v[0])))  # sort by z, y, x values
# array([[1. , 0. , 0. ],
#        [0.5, 0.5, 0. ],
#        [0. , 1. , 0. ],
#        [0. , 0. , 1. ]])

A_rotated = np.array(sorted(A @ R.T, key=lambda v: (v[2], v[1], v[0])))
# array([[-1. ,  0. ,  0. ],   # no match
#        [-0.5,  0.5,  0. ],   # no match
#        [ 0. ,  1. ,  0. ],   # match
#        [ 0. ,  0. ,  1. ]])  # match

(Этот подход делает два вида, поэтому O (n ln (n))?) Третья идея заключается в сравнении наборов , созданных из оригинальные и повернутые векторы. У меня есть ощущение, что это так же хорошо, как сравнивать отсортированные векторы.

Но остается одно: как справиться с приближенным сравнением? Я хочу принять два вектора v и w равными, если, например, np.allclose(v, w) == True или эквивалент (т. Е. abs(v - w) < eps или аналогичный):

np.allclose([1, 0, 0], [1, 0, 0])
# True
np.allclose([1, 0, 0], [1 + 1e-5, 0, 0], atol=1e-5)
# True
np.allclose([1, 0, 0], [1 + 1e-4, 0, 0], atol=1e-5)
# False

Так что вот вопрос : как (эффективно) сравнить два (неупорядоченных) набора векторов на равенство с учетом числового приближения (например, np.allclose)?

Answer 1

Это просто, вы преобразуете все значения ваших векторов, которые <atol, в 0. Вы можете сделать это, используя numpy.vectorize, ищите do c здесь .

import numpy as np

def transform(x, atol):
    if x>0 and x-1<atol:
        return 1
    else:
        return x

myarray = np.array([[1, 0, 0], [1 + 1e-4, 0, 0]])
vf = np.vectorize(transform)
new_array = vf(myarray, atol=1e-5)

Теперь вы можете проверить свою симметрию.

Пожалуйста, скажите мне, если я ответил на ваш вопрос.

ОБНОВЛЕНИЕ

Я вижу, у вас есть функция isclose() в numpy, Вы ДОЛЖНЫ использовать его, а не мою функцию с нуля.

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

Answer 2

Вот функция, которая работает с использованием np.lexsort:

def is_symmetric(A, R, *args, **kwargs):
    A = np.asanyarray(A)
    A = A[np.lexsort(A.T)]

    A_t = A @ np.asanyarray(R).T
    A_t = A_t[np.lexsort(A_t.T)]
    return np.allclose(A, A_t, *args, **kwargs)

Некоторые результаты:

R = np.array([[0, -1, 0],  # 90° rotation as an example
              [1,  0, 0],
              [0,  0, 1]])

is_symmetric([[0, 0, 0]], R)
# True
is_symmetric([[1, 0, 0],
              [0, 1, 0],
              [0, 0, 0]], R)
# False
is_symmetric([[1, 0, 0],
              [0, 1, 0],
              [0, 0, 0],
              [-1, 0, 0]], R)
# False
is_symmetric([[1, 0, 0],
              [0, 1, 0],
              [0, 0, 0],
              [-1, 0, 0],
              [0, -1, 0]], R)
# True

---

Производительность кажется хорошей для 100000 случайных векторов:

A = np.random.rand(100000, 3)
%timeit is_symmetric(A, R)
# 82.2 ms ± 75.4 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)