如何有效地比较两组无序向量（`np.ndarray`）？

Question

我试图让我的问题更清楚。老题外话到此为止还能找到

问题：我有一个 n x 3 矩阵 A (np.ndarray) 的 n 点在三个维度.如果这些点作为无序集合是静止的，我们说这些点关于变换 R（3 x 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.

（可能的一些讨论以及我的疑惑和尝试见下文）

老题材:

我想检查以向量表示的点集合中的对称性。这意味着检查这些点是否关于 space 中矩阵变换的应用是不变的，例如旋转或平面镜像。

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 执行此操作，查找文档 here.

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)

现在您可以进行对称性验证了。

如果我回答了你的问题，请告诉我。

更新

我看到您在 numpy 中已经有了函数 isclose()，您应该使用它，而不是从头开始我的函数。

不过，我不会删除我的答案，以保持与之相关的评论。

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)

如何有效地比较两组无序向量（`np.ndarray`）？

How to efficiently compare two sets of unordered vectors (`np.ndarray`)?

python

numpy

vector

comparison

numpy-ndarray