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

Question

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

例如，给定bin索引7，封闭的网格点索引将是(1, 2, 5, 6)。你知道吗

我正在寻找一种解决方案，它应该适用于n维数组，而不仅仅是2D数组。我觉得这应该是一个经常出现的问题，但是在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

我有个解决办法，我早该想到的。如果你先解开索引，一切就容易多了。我已经用解开的索引注释了我的原图。你知道吗

展开的bin索引始终是网格中最远的一角，因此您可以采用在每个维度中减去一个位置的所有组合来查找所有其他边。这可以通过itertools.product轻松快速地完成。注意，在使用索引时必须小心，因为查询网格之外的bin（例如bin_idx=0或4）将返回无效的索引。这可以在实际查询时用try和except块来处理，如@alec\u 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))

Answer 2

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

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]})

然后在dict的值中查找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 3

我终于想出了一种不需要建立查找表的替代方法。 但是，您需要重新调整阵列以使其正常工作。你知道吗

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