从 nd 数组中的 bin 索引中查找封闭网格点的索引

Question

我有一个 nd 网格点数组 G，然后是一个覆盖的 nd 数组 bin B，如下图所示。 G 的索引显示为蓝色，B 的索引显示为红色。给定 bin（红色）的索引，我想找到封闭网格点（蓝色）的索引。

例如，给定 bin 索引 7，封闭的网格点索引将为 (1, 2, 5, 6).

我正在寻找适用于 n 维数组的解决方案，而不仅仅是二维数组。我觉得这应该是一个经常出现的问题，但在 numpy 中还没有找到任何解决方案，并且正在努力为 n 维提出一个优雅的解决方案。

请注意，B 的索引数在每个数组维度上比 G 多一个。

一些测试代码

import numpy as np
G = np.arange(3*4).reshape(3, 4)
B = np.arange(4*5).reshape(4, 5)
idx = 7

Answer 1

您可以使用以下代码构建一个字典来关联索引。

from collections import defaultdict

#Map indices
d = defaultdict(list)
for n,row in enumerate(G):
    for i,idx in enumerate(row):
        for j in range(2): #check current and next row
            d[idx].append(B[n+j][i]) #current row
            try:  #next row (or next number) may not exist
                #next row
                #[i+1] is the index of the next number in the row
                d[idx].append(B[n+j][i+1]) 
            except IndexError:
                pass

这将创建

>>> d
defaultdict(list,
            {0: [0, 1, 5, 6],
             1: [1, 2, 6, 7],
             2: [2, 3, 7, 8],
             3: [3, 4, 8, 9],
             4: [5, 6, 10, 11],
             5: [6, 7, 11, 12],
             6: [7, 8, 12, 13],
             7: [8, 9, 13, 14],
             8: [10, 11, 15, 16],
             9: [11, 12, 16, 17],
             10: [12, 13, 17, 18],
             11: [13, 14, 18, 19]})

然后在字典的值中寻找idx。

#Search value
idx = 7 #red bin
r = []
for k,v in d.items():
    if idx in v:
        r.append(k)

结果：

>>> print(r) #blue bins sorrounding idx
[1, 2, 5, 6]

Answer 2

我终于想出了一个不需要构建查找的替代方法 table。但是，您需要重新调整数组的形状才能使其正常工作。

red = np.array([[np.nan, x] for row in B for x in row]).reshape(4,10)
blue = np.array([[x,np.nan] for row in G for x in row]).reshape(3,8)


def f(red, blue, idx):
    i,j = [n[0] for n in np.where(red==idx)]
    r = []
    k = max(0,i-1)
    w = max(0,j-3)
    try:
        r.append(blue[k][w:j])
    except IndexError:
        pass
    try:
        r.append(blue[i][w:j])
    except IndexError:
        pass
    r = set([int(n) for n in flatten(r) if not np.isnan(n)])
    return r



for idx in range(20):
    print(idx, f(red, blue, idx))

结果是：

0 {0}
1 {0, 1}
2 {1, 2}
3 {2, 3}
4 {3}
5 {0, 4}
6 {0, 1, 4, 5}
7 {1, 2, 5, 6}
8 {2, 3, 6, 7}
9 {3, 7}
10 {8, 4}
11 {8, 9, 4, 5}
12 {9, 10, 5, 6}
13 {10, 11, 6, 7}
14 {11, 7}
15 {8}
16 {8, 9}
17 {9, 10}
18 {10, 11}
19 {11}

这里是 flatten()

的代码

def flatten(l):
    '''
    Flat an iterable.
    '''
    for item in l:
        try:
            yield from flatten(item)
        except TypeError:
            yield item

Answer 3

我有一个解决方案，我早该想到的。如果您先解开索引，一切都会容易得多。我用展开的索引注释了我的原始绘图。

展开的 bin-index 总是网格最远的角，所以你可以采取在每个维度上减去一个位置的所有组合，找到所有其他边缘。使用 itertools.product 可以轻松快速地完成此操作。请注意，使用索引时必须小心，因为查询网格外的 bin（例如 bin_idx=0 或 4）将 return 无效索引。这可以在实际查询时使用 try 和 except 块来处理，如@alec_djinn 的答案。

import numpy as np
import itertools as it


def get_grid_indices(bin_idx, bins_shape):
    bin_nrvld = np.unravel_index(bin_idx, bins_shape)
    grid_indices = list()
    dims = len(bins_shape)
    index_offsets = it.product([0, -1], repeat=dims)
    for offset in index_offsets:
        grid_indices.append(tuple(x + y for x, y in zip(bin_nrvld, offset)))
    return grid_indices


print('Two dimensional example')
blue_grid = np.arange(3*4).reshape(3, 4)
red_bins = np.arange(4*5).reshape(4, 5)
bin_idx = 7
grid_indices = get_grid_indices(bin_idx, red_bins.shape)
for idx in grid_indices:
    print('index: '+str(blue_grid[idx])+', unraveled: ', end='')
    print(np.unravel_index(blue_grid[idx], blue_grid.shape))

print('')
print('Three dimensional example')

blue_grid = np.arange(2*2*2).reshape(2, 2, 2)
red_bins = np.arange(3*3*3).reshape(3, 3, 3)
bin_idx = 13
grid_indices = get_grid_indices(bin_idx, red_bins.shape)

for idx in grid_indices:
    print('index: '+str(blue_grid[idx])+', unraveled: ', end='')
    print(np.unravel_index(blue_grid[idx], blue_grid.shape))

从 nd 数组中的 bin 索引中查找封闭网格点的索引

Find indices of enclosing grid-points from bin index in an nd-array

python

arrays

indexing

numpy-ndarray