python / NumPy : Build 2D array without adding duplicate rows (for triangular mesh)

Question

我正在编写一些操纵 3D 三角形网格的代码。导入网格数据后，我需要“统一”空间中同一点的顶点。

我一直假设 numpy 数组是存储和操作数据的最快方式，但我似乎无法找到一种既能快速构建顶点列表又能避免添加重复条目的方法。

因此，为了测试方法，创建一个包含 10000 个唯一行的 3x30000 数组:

import numpy as np
points = np.random.random((10000,3))
raw_data = np.concatenate((points,points,points))
np.random.shuffle(raw_data)

这是网格数据的一个很好的近似值，每个点作为一个面顶点出现 3 次。在统一时，我需要构建一个唯一顶点列表；如果一个点已经在列表中，则必须存储对它的引用。

到目前为止，我使用 numpy 得到的最好结果如下:

def unify(raw_data):
    # first point must be new
    unified_verts = np.zeros((1,3),dtype=np.float64)
    unified_verts[0] = raw_data[0]
    ref_list = [0]

    for i in range(1,len(raw_data)):
        point = raw_data[i]     
        index_array = np.where(np.all(point==unified_verts,axis=1))[0]

        # point not in array yet
        if len(index_array) == 0:
            point = np.expand_dims(point,0)
            unified_verts = np.concatenate((unified_verts,point))
            ref_list.append(len(unified_verts)-1)

        # point already exists
        else:
            ref_list.append(index_array[0])

    return unified_verts, ref_list

使用 cProfile 进行测试:

import cProfile
cProfile.run("unify(raw_data)")

在我的机器上，它运行了 5.275 秒。我虽然使用 Cython 来加速它，但从我读过的内容来看，Cython 通常不会比 numpy 方法运行得快得多。关于如何更有效地执行此操作的任何建议？

Answer 1

Jaime has shown a neat trick可用于将二维数组视为一维数组，其中的项对应于二维数组的行。这个技巧可以让您将以一维数组作为输入的 numpy 函数(例如 np.unique)应用到更高维的数组。

如果 unified_verts 中行的顺序无关紧要(只要 ref_list 相对于 unifed_verts 是正确的)，那么您可以使用 np .unique 连同 Jaime 的技巧如下:

def unify2(raw_data):
    dtype = np.dtype((np.void, (raw_data.shape[1] * raw_data.dtype.itemsize)))
    uniq, inv = np.unique(raw_data.view(dtype), return_inverse=True)
    uniq = uniq.view(raw_data.dtype).reshape(-1, raw_data.shape[1])
    return uniq, inv

从 raw_data 可以从 unify(或 unify2)的返回值重建的意义上来说，结果是相同的:

unified, ref = unify(raw_data)
uniq, inv = unify2(raw_data)
assert np.allclose(uniq[inv], unified[ref])  # raw_data

在我的机器上，unified, ref = unify(raw_data) 需要大约 51.390s，而 uniq, inv = unify2(raw_data) 需要大约 0.133s (~ 386x加速)。