Making grid triangular mesh quickly with Numpy
We could play a multi-dimensional
game based on slicing
and multi-dim assignment
that are perfect in NumPy environment on efficiency -
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
Runtime test and verification -
In [226]: Nr,Nc = 100, 100In [227]: np.allclose(MakeFaces(Nr, Nc), MakeFacesVectorized1(Nr, Nc))Out[227]: TrueIn [228]: %timeit MakeFaces(Nr, Nc)100 loops, best of 3: 11.9 ms per loopIn [229]: %timeit MakeFacesVectorized1(Nr, Nc)10000 loops, best of 3: 133 µs per loopIn [230]: 11900/133.0Out[230]: 89.47368421052632
Around 90x
speedup for Nr, Nc = 100, 100
!
You can achieve a similar result without any explicit loops if you recast the problem correctly. One way would be to imagine the result as three arrays, each containing one of the vertices: first, second and third. You can then zip up or otherwise convert the arrays into whatever format you like in a fairly inexpensive operation.
You start with the actual matrix. This will make indexing and selecting elements much easier:
m = np.arange(Nr * Nc).reshape(Nr, Nc)
The first array will contain all the 90-degree corners:
c1 = np.concatenate((m[:-1, :-1].ravel(), m[1:, 1:].ravel()))
m[:-1, :-1]
are the corners that are at the top, m[1:, 1:]
are the corners that are at the bottom.
The second array will contain the corresponding top acute corners:
c2 = np.concatenate((m[:-1, 1:].ravel(), m[:-1, 1:].ravel()))
And the third array will contain the bottom corners:
c2 = np.concatenate((m[1:, :-1].ravel(), m[1:, :-1].ravel()))
You can now get an array like your original one back by zipping:
faces = list(zip(c1, c2, c3))
I am sure that you can find ways to improve this algorithm, but it is a start.