使用 Numpy 快速制作网格三角形网格
Making grid triangular mesh quickly with Numpy
考虑一个表示节点编号的正则矩阵,如图所示:
我想列出图中所有三角形的列表。这将导致以下二维列表:[[0,1,4],[1,5,4],[1,2,5],[2,6,5],...,[11,15,14]]
假设矩阵的维度为 (Nr
XNc
)(在本例中为 (4X4)),我可以使用以下代码实现此结果:
def MakeFaces(Nr,Nc):
Nfaces=(Nr-1)*(Nc-1)*2
Faces=np.zeros((Nfaces,3),dtype=np.int32)
for r in range(Nr-1):
for c in range(Nc-1):
fi=(r*(Nc-1)+c)*2
l1=r*Nc+c
l2=l1+1
l3=l1+Nc
l4=l3+1
Faces[fi]=[l1,l2,l3]
Faces[fi+1]=[l2,l4,l3]
return Faces
但是,双循环操作使这种方法非常慢。有没有一种以智能方式使用 numpy 来更快地完成此操作的方法?
如果你正确地重写问题,你可以在没有任何显式循环的情况下获得类似的结果。一种方法是将结果想象成三个数组,每个数组包含一个顶点:第一、第二和第三。然后,您可以压缩或以其他方式将数组转换为您喜欢的任何格式,操作成本相当低。
您从实际矩阵开始。这将使索引和选择元素变得更加容易:
m = np.arange(Nr * Nc).reshape(Nr, Nc)
第一个数组将包含所有 90 度角:
c1 = np.concatenate((m[:-1, :-1].ravel(), m[1:, 1:].ravel()))
m[:-1, :-1]
是顶部的角,m[1:, 1:]
是底部的角。
第二个数组将包含相应的顶部锐角:
c2 = np.concatenate((m[:-1, 1:].ravel(), m[:-1, 1:].ravel()))
第三个数组将包含底角:
c2 = np.concatenate((m[1:, :-1].ravel(), m[1:, :-1].ravel()))
您现在可以通过压缩获得与原始阵列相同的阵列:
faces = list(zip(c1, c2, c3))
我相信您可以找到改进此算法的方法,但这只是一个开始。
我们可以玩一个基于 slicing
和 multi-dim assignment
的 multi-dimensional
游戏,在 NumPy 环境中效率完美 -
def MakeFacesVectorized1(Nr,Nc):
out = np.empty((Nr-1,Nc-1,2,3),dtype=int)
r = np.arange(Nr*Nc).reshape(Nr,Nc)
out[:,:, 0,0] = r[:-1,:-1]
out[:,:, 1,0] = r[:-1,1:]
out[:,:, 0,1] = r[:-1,1:]
out[:,:, 1,1] = r[1:,1:]
out[:,:, :,2] = r[1:,:-1,None]
out.shape =(-1,3)
return out
运行时测试和验证-
In [226]: Nr,Nc = 100, 100
In [227]: np.allclose(MakeFaces(Nr, Nc), MakeFacesVectorized1(Nr, Nc))
Out[227]: True
In [228]: %timeit MakeFaces(Nr, Nc)
100 loops, best of 3: 11.9 ms per loop
In [229]: %timeit MakeFacesVectorized1(Nr, Nc)
10000 loops, best of 3: 133 µs per loop
In [230]: 11900/133.0
Out[230]: 89.47368421052632
90x
左右 Nr, Nc = 100, 100
!
加速
考虑一个表示节点编号的正则矩阵,如图所示:
我想列出图中所有三角形的列表。这将导致以下二维列表:[[0,1,4],[1,5,4],[1,2,5],[2,6,5],...,[11,15,14]]
假设矩阵的维度为 (Nr
XNc
)(在本例中为 (4X4)),我可以使用以下代码实现此结果:
def MakeFaces(Nr,Nc):
Nfaces=(Nr-1)*(Nc-1)*2
Faces=np.zeros((Nfaces,3),dtype=np.int32)
for r in range(Nr-1):
for c in range(Nc-1):
fi=(r*(Nc-1)+c)*2
l1=r*Nc+c
l2=l1+1
l3=l1+Nc
l4=l3+1
Faces[fi]=[l1,l2,l3]
Faces[fi+1]=[l2,l4,l3]
return Faces
但是,双循环操作使这种方法非常慢。有没有一种以智能方式使用 numpy 来更快地完成此操作的方法?
如果你正确地重写问题,你可以在没有任何显式循环的情况下获得类似的结果。一种方法是将结果想象成三个数组,每个数组包含一个顶点:第一、第二和第三。然后,您可以压缩或以其他方式将数组转换为您喜欢的任何格式,操作成本相当低。
您从实际矩阵开始。这将使索引和选择元素变得更加容易:
m = np.arange(Nr * Nc).reshape(Nr, Nc)
第一个数组将包含所有 90 度角:
c1 = np.concatenate((m[:-1, :-1].ravel(), m[1:, 1:].ravel()))
m[:-1, :-1]
是顶部的角,m[1:, 1:]
是底部的角。
第二个数组将包含相应的顶部锐角:
c2 = np.concatenate((m[:-1, 1:].ravel(), m[:-1, 1:].ravel()))
第三个数组将包含底角:
c2 = np.concatenate((m[1:, :-1].ravel(), m[1:, :-1].ravel()))
您现在可以通过压缩获得与原始阵列相同的阵列:
faces = list(zip(c1, c2, c3))
我相信您可以找到改进此算法的方法,但这只是一个开始。
我们可以玩一个基于 slicing
和 multi-dim assignment
的 multi-dimensional
游戏,在 NumPy 环境中效率完美 -
def MakeFacesVectorized1(Nr,Nc):
out = np.empty((Nr-1,Nc-1,2,3),dtype=int)
r = np.arange(Nr*Nc).reshape(Nr,Nc)
out[:,:, 0,0] = r[:-1,:-1]
out[:,:, 1,0] = r[:-1,1:]
out[:,:, 0,1] = r[:-1,1:]
out[:,:, 1,1] = r[1:,1:]
out[:,:, :,2] = r[1:,:-1,None]
out.shape =(-1,3)
return out
运行时测试和验证-
In [226]: Nr,Nc = 100, 100
In [227]: np.allclose(MakeFaces(Nr, Nc), MakeFacesVectorized1(Nr, Nc))
Out[227]: True
In [228]: %timeit MakeFaces(Nr, Nc)
100 loops, best of 3: 11.9 ms per loop
In [229]: %timeit MakeFacesVectorized1(Nr, Nc)
10000 loops, best of 3: 133 µs per loop
In [230]: 11900/133.0
Out[230]: 89.47368421052632
90x
左右 Nr, Nc = 100, 100
!