Geek Answers Handbook

Python, regular grid neighbors

Suppose I have a set of 2D coordinates that represent the cell centers of a two-dimensional regular grid. I would like to find for each grid cell two nearest neighbors in each direction.

The problem is quite simple if each one assigns to each cell an index defined as follows:

idx_cell = idx + N * idy

where N is the total number of cells in the grid, idx = x / dx and idy = y / dx, where x and y are the x coordinate and y coordinate of the cell, and dx is its size.

For example, neighboring cells for a cell with idx_cell = 5 are cells with idx_cell equal to 4.6 (for the x axis) and 5 + N, 5-N (for the y axis).

The problem is that my implementation of the algorithm is rather slow for large (N> 1e6) datasets.

For example, to get the neighboring x axes, do

[x[(idx_cell==idx_cell[i]-1)|(idx_cell==idx_cell[i]+1)] for i in cells]

What do you think is the fastest way to implement this algorithm?

+3
source share
1 answer

You basically reinvent the indexing scheme of a multidimensional array. It is relatively easy to code, but you can use the two functions unravel_indexand ravel_multi_indexto your advantage.

If your grid has columns Mand columns Nto get idxand idyone item that you could do:

>>> M, N = 12, 10
>>> np.unravel_index(4, dims=(M, N))
(0, 4)

This also works if, instead of a single index, you provide an array of indexes:

>>> np.unravel_index([15, 28, 32, 97], dims=(M, N))
(array([1, 2, 3, 9], dtype=int64), array([5, 8, 2, 7], dtype=int64))

So, if it cellshas multiple cell indices, you want to find neighbors:

>>> cells = np.array([15, 28, 32, 44, 87])

You can get your neighbors as:

>>> idy, idx = np.unravel_index(cells, dims=(M, N))
>>> neigh_idx = np.vstack((idx-1, idx+1, idx, idx))
>>> neigh_idy = np.vstack((idy, idy, idy-1, idy+1))
>>> np.ravel_multi_index((neigh_idy, neigh_idx), dims=(M,N))
array([[14, 27, 31, 43, 86],
       [16, 29, 33, 45, 88],
       [ 5, 18, 22, 34, 77],
       [25, 38, 42, 54, 97]], dtype=int64)

Or, if you prefer it like this:

>>> np.ravel_multi_index((neigh_idy, neigh_idx), dims=(M,N)).T
array([[14, 16,  5, 25],
       [27, 29, 18, 38],
       [31, 33, 22, 42],
       [43, 45, 34, 54],
       [86, 88, 77, 97]], dtype=int64)

: ravel_multi_index mode, , . .

+2

More articles:


All Articles