在每个点的 numpy 矩阵中获取已知边界内的所有坐标点

Question

给定以下 numpy 矩阵

import numpy as np

np_matrix = np.array(
[[0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,3,0,2,0,0,1,0,0,0,0,0,0]
,[0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,3,0,2,2,0,0,0,0,0,0,0,0]
,[0,0,0,3,0,0,0,0,2,2,2,0,0,0,0,0,3,0,0,0,3,0,0,2,2,2,2,2,2,2,2,2]
,[0,0,0,3,0,0,0,2,0,0,0,2,0,0,0,0,3,0,0,0,3,3,0,0,0,0,0,0,0,0,0,0]
,[0,0,0,3,0,0,2,0,1,0,0,0,2,0,0,0,3,0,0,0,0,3,3,3,3,3,0,0,0,0,0,0]
,[0,0,0,3,0,0,2,0,0,0,0,0,2,0,0,0,3,0,0,0,0,0,0,0,0,3,3,3,3,3,3,3]
,[0,0,0,3,0,0,2,0,0,0,0,0,2,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
,[0,0,0,0,3,0,0,2,0,0,0,2,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
,[0,0,0,0,3,0,0,0,2,2,2,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
,[0,0,0,0,0,3,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
,[0,0,0,0,0,0,3,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
,[3,3,3,3,0,0,0,3,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
,[0,0,0,3,0,0,0,0,3,3,3,3,0,0,0,0,0,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0]
,[0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,3,3,3,0,0,3,3,3,3,0,0,0,0,0,0,0,0]
,[0,0,0,0,3,3,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0]
,[0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,3,0,0,2,2,2,0,0,3,0,0,0,0,0,0,0,0]
,[2,2,2,0,0,3,0,0,0,0,0,0,0,0,0,3,0,0,2,1,2,0,0,3,0,0,0,0,0,0,0,0]
,[0,0,2,2,0,3,3,0,0,0,0,0,0,0,0,3,3,0,2,2,2,0,0,3,0,0,0,0,0,0,0,0]
,[0,0,0,2,0,0,3,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0]
,[1,0,0,2,0,0,3,0,0,0,0,0,0,0,0,0,3,3,0,0,0,0,3,0,0,0,0,0,0,0,0,0]
,[0,0,0,2,0,0,3,0,0,0,0,0,0,0,0,0,0,3,3,0,3,3,0,0,0,0,0,0,0,0,0,0]
,[0,0,0,2,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,3,3,0,0,0,0,0,0,0,0,0,0,0]
,[0,0,2,2,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
,[2,2,2,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
,[0,0,0,0,0,3,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,3,3,3,3,3,3,3]
,[0,0,0,0,0,3,0,0,0,0,0,0,3,3,3,3,3,3,3,3,0,0,0,0,3,0,0,0,0,0,0,0]
,[0,0,0,3,3,0,0,0,0,3,3,3,3,2,2,2,2,2,2,3,3,0,0,0,3,0,0,0,0,0,2,2]
,[3,3,3,3,0,0,0,0,0,3,2,2,2,0,0,0,0,0,2,2,3,0,0,0,3,0,0,0,2,2,2,0]
,[0,0,0,0,0,0,0,0,0,3,2,0,0,0,0,0,0,0,0,2,3,0,0,0,3,0,0,2,2,0,0,0]
,[0,0,0,0,0,0,0,0,0,3,2,0,0,0,1,0,0,0,0,2,3,0,0,0,3,0,0,2,0,0,0,1]]
)

可以用这样的图片直观地呈现出来：

其中红点从左到右编号，可以使用以下函数在矩阵中识别。感谢@DanielF

def getRedDotsCoordinatesFromLeftToRight(np_matrix, red_dor_number=1):
    red_dots = np.where(np_matrix == red_dor_number)
    red_dots = tuple(g[np.argsort(red_dots[-1])] for g in red_dots)
    red_dots = np.stack(red_dots)[::-1].T
    return red_dots

red_dots = getRedDotsCoordinatesFromLeftToRight(np_matrix)
print(red_dots)

red_dots = np.array(
    [[ 0, 25],
    [ 4,  8],
    [16, 19],
    [19,  0],
    [29, 14],
    [29, 31]]
)

两个问题：

问题一：如何识别所有的白点坐标（标有 0)在绿色边界内(标记为2)位于红点(标记为1) ?
问题2：如何识别所有的白点坐标（标有 0)黑色边界（标记为3）和绿色边界 （标有 2） 位于红点 （标有 1) ?

我正在为这个示例矩阵寻找这个结果：

space_within_greenDots = np.array(
    [[[17,  0], [17,  1], [18,  0], [18,  1], [18,  2], [19,  1], [19,  2], [20,  0], [20,  1], [20,  2], [21,  0], [21,  1], [21,  2], [22,  0], [22,  1]],
    [[ 3,  8], [ 3,  9], [ 3, 10], [ 4,  7], [ 4,  9], [ 4, 10], [ 4, 11], [ 5,  7], [ 5,  8], [ 5,  9], [ 5, 10], [ 5, 11], [ 6,  7], [ 6,  8], [ 6,  9], [ 6, 10], [ 6, 11], [ 7,  8], [ 7,  9], [ 7, 10]],
    [[27, 13], [27, 14], [27, 15], [27, 16], [27, 17], [28, 11], [28, 12], [28, 13], [28, 14], [28, 15], [28, 16], [28, 17], [28, 18], [29, 11], [29, 12], [29, 13], [29, 15], [29, 16], [29, 17], [29, 18]],
    [],
    [[ 0, 23], [ 0, 24], [ 0, 26], [ 0, 27], [ 0, 28], [ 0, 29], [ 0, 30], [ 0, 31], [ 1, 24], [ 1, 25], [ 1, 26], [ 1, 27], [ 1, 28], [ 1, 29], [ 1, 30], [ 1, 31]],
    [[27, 31], [28, 29], [28, 30], [28, 31], [29, 28], [29, 29], [29, 30]]],
)    


space_between_darkDots_and_greenDots = np.array(
    [ [[12,  0], [12,  1], [12,  2], [13,  0], [13,  1], [13,  2], [13,  3], [14,  0], [14,  1], [14,  2], [14,  3], [15,  0], [15,  1], [15,  2], [15,  3], [15,  4], [16,  3], [16,  4], [17,  4], [18,  4], [18,  5], [19,  4], [19,  5], [20,  4], [20,  5], [21,  4], [21,  5], [22,  4], [22,  5], [23,  3], [23,  4], [23,  5], [24,  0], [24,  1], [24,  2], [24,  3], [24,  4], [25,  0], [25,  1], [25,  2], [25,  3], [25,  4], [26,  0], [26,  1], [26,  2]],
    [[ 0,  4], [ 0,  5], [ 0,  6], [ 0,  7], [ 0,  8], [ 0,  9], [ 0, 10], [ 0, 11], [ 0, 12], [ 0, 13], [ 0, 14], [ 0, 15], [ 1,  4], [ 1,  5], [ 1,  6], [ 1,  7], [ 1,  8], [ 1,  9], [ 1, 10], [ 1, 11], [ 1, 12], [ 1, 13], [ 1, 14], [ 1, 15], [ 2,  4], [ 2,  5], [ 2,  6], [ 2,  7], [ 2, 11], [ 2, 12], [ 2, 13], [ 2, 14], [ 2, 15], [ 3,  4], [ 3,  5], [ 3,  6], [ 3, 12], [ 3, 13], [ 3, 14], [ 3, 15], [ 4,  4], [ 4,  5], [ 4, 13], [ 4, 14], [ 4, 15], [ 5,  4], [ 5,  5], [ 5, 13], [ 5, 14], [ 5, 15], [ 6,  4], [ 6,  5], [ 6, 13], [ 6, 14], [ 6, 15], [ 7,  5], [ 7,  6], [ 7, 12], [ 7, 13], [ 7, 14], [ 8,  5], [ 8,  6], [ 8,  7], [ 8, 11], [ 8, 12], [ 8, 13], [ 8, 14], [ 9,  6], [ 9,  7], [ 9,  8], [ 9,  9], [ 9, 10], [ 9, 11], [ 9, 12], [ 9, 13], [10,  7], [10,  8], [10,  9], [10, 10], [10, 11], [10, 12], [11,  8], [11,  9], [11, 10], [11, 11]],
    [],
    [[13, 18], [13, 19], [14, 16], [14, 17], [14, 18], [14, 19], [14, 20], [14, 21], [14, 22], [15, 16], [15, 17], [15, 21], [15, 22], [16, 16], [16, 17], [16, 21], [16, 22], [17, 17], [17, 21], [17, 22], [18, 17], [18, 18], [18, 19], [18, 20], [18, 21], [18, 22], [19, 18], [19, 19], [19, 20], [19, 21], [20, 19]],
    [[ 0, 21], [ 1, 21], [ 2, 21], [ 2, 22], [ 3, 22], [ 3, 23], [ 3, 24], [ 3, 25], [ 3, 26], [ 3, 27], [ 3, 28], [ 3, 29], [ 3, 30], [ 3, 31], [ 4, 26], [ 4, 27], [ 4, 28], [ 4, 29], [ 4, 30], [ 4, 31]],
    [[25, 25], [25, 26], [25, 27], [25, 28], [25, 29], [25, 30], [25, 31], [26, 25], [26, 26], [26, 27], [26, 28], [26, 29], [27, 25], [27, 26], [27, 27], [28, 25], [28, 26], [29, 25], [29, 26]],
    ]
)

一些假设：

矩阵形状可以变化。不是固定尺寸。
红点的数量因矩阵而异。但是还有矩阵中总是至少有一个红点。¨

Answer 1

问题1使用递归floodfill算法的解决方案：

参见JavaScript demonstration I made. GitHub Source中的floodfill算法。

我首先创建了一个 floodfill 函数，它的工作方式就像一个绘画程序，即当给定封闭区域中的一个点时，将用一种颜色填充该区域直到边界。

然后，所有需要做的就是遍历每个红色像素（值1）并用索引红点的颜色填充到绿色像素（值2）我们在（这样我们可以稍后单独获取区域）。

然后，我们简单地使用您的 red_dots 程序的一个版本，我将其修改得更通用一些，以获得白色像素所有坐标的结果。

这最后一步是在一行中完成的。它将所有内容转换为一个大列表，其中每个子列表包含一个白色像素区域的坐标。

请注意我们必须如何在末尾以列表结束，因为这不是矩形，所以不能使用 numpy 数组（除非我们使用 dtype=object）。

无论如何，这是代码：

import numpy as np

def inArrBounds(arr, c):
    return 0 <= c[0] < arr.shape[1] and 0 <= c[1] < arr.shape[0]

def floodfill(arr, start, fillCol, edgeCol):
    if arr[start[1],start[0]] in (fillCol, edgeCol):
        return
    arr[start[1], start[0]] = fillCol
    for p in ((start[0]+1, start[1]),
              (start[0]-1, start[1]), 
              (start[0], start[1]+1),
              (start[0], start[1]-1)):
        if inArrBounds(arr, p):
            floodfill(arr, p, fillCol, edgeCol)

def coordsLtR(arr, val):
    pnts = np.where(arr == val)
    pnts = tuple(g[np.argsort(pnts[-1])] for g in pnts)
    pnts = np.stack(pnts)[::-1].T
    return pnts

red_dots = coordsLtR(np_matrix, 1)
for i, dot in enumerate(red_dots):
    floodfill(np_matrix, dot, i+4, 2)
    np_matrix[dot[1], dot[0]] = 1

regions = [coordsLtR(np_matrix,i+4)[:,::-1].tolist() for i in range(len(red_dots))]

创建 regions 列表为：

[[17, 0], [18, 0], [20, 0], [21, 0], [22, 0], [17, 1], [18, 1], [19, 1], [20, 1], [21, 1], [22, 1], [18, 2], [19, 2], [20, 2], [21, 2]]
[[4, 7], [6, 7], [5, 7], [3, 8], [7, 8], [6, 8], [5, 8], [6, 9], [7, 9], [5, 9], [4, 9], [3, 9], [5, 10], [4, 10], [3, 10], [6, 10], [7, 10], [5, 11], [6, 11], [4, 11]]
[[28, 11], [29, 11], [29, 12], [28, 12], [27, 13], [29, 13], [28, 13], [27, 14], [28, 14], [29, 15], [28, 15], [27, 15], [27, 16], [29, 16], [28, 16], [28, 17], [29, 17], [27, 17], [28, 18], [29, 18]]
[]
[[0, 23], [0, 24], [1, 24], [1, 25], [0, 26], [1, 26], [0, 27], [1, 27], [0, 28], [1, 28], [0, 29], [1, 29], [0, 30], [1, 30], [0, 31], [1, 31]]
[[29, 28], [28, 29], [29, 29], [28, 30], [29, 30], [27, 31], [28, 31]]

为了形象化 np_matrix 中的填充区域，这里是 matplotlib 绘图的屏幕截图：

问题2的解答

第二部分的逻辑保持不变，只是我们必须按正确的顺序做事。我这样做的方法是用一种颜色填充到黑色边框，然后从中减去白色区域和绿色边框。

因此，我们需要使用单独的 np_matrix，以免干扰第一个。可以使用 np.copy.

制作副本

然后我们需要从红点填充到黑色边框，然后从这个填充的区域，减去所有在白色区域或绿色区域的坐标.

所以，使用上面相同的函数，代码如下：

def validBlackCoord(c):
    return not (any(c in s for s in white_regions) or np_matrix[c[0],c[1]] == 2)

red_dots = coordsLtR(np_matrix, 1)
white_matrix = np.copy(np_matrix)
for i, dot in enumerate(red_dots):
    floodfill(white_matrix, dot, i+4, 2)
    white_matrix[dot[1], dot[0]] = 1

white_regions = [coordsLtR(white_matrix,i+4)[:,::-1].tolist() for i in range(len(red_dots))]

black_matrix = np.copy(np_matrix)
for i, dot in enumerate(red_dots):
    floodfill(black_matrix, dot, i+4, 3)
    black_matrix[dot[1], dot[0]] = 1

black_regions = [coordsLtR(black_matrix,i+4)[:,::-1].tolist() for i in range(len(red_dots))]

black_regions = [list(filter(key=validBlackCoord, r)) for r in black_regions]

创建两个列表，white_regions与上面相同，black_regions是：

[[12, 0], [24, 0], [15, 0], [25, 0], [14, 0], [13, 0], [26, 0], [24, 1], [15, 1], [14, 1], [25, 1], [13, 1], [12, 1], [26, 1], [24, 2], [25, 2], [26, 2], [12, 2], [15, 2], [13, 2], [14, 2], [24, 3], [14, 3], [15, 3], [23, 3], [16, 3], [13, 3], [25, 3], [22, 4], [19, 4], [21, 4], [15, 4], [17, 4], [23, 4], [25, 4], [20, 4], [18, 4], [24, 4], [16, 4], [22, 5], [21, 5], [20, 5], [18, 5], [23, 5], [19, 5]]
[[0, 4], [6, 4], [5, 4], [4, 4], [3, 4], [2, 4], [1, 4], [8, 5], [7, 5], [6, 5], [4, 5], [3, 5], [2, 5], [5, 5], [1, 5], [0, 5], [1, 6], [3, 6], [9, 6], [0, 6], [7, 6], [8, 6], [2, 6], [8, 7], [9, 7], [2, 7], [10, 7], [0, 7], [1, 7], [0, 8], [1, 8], [9, 8], [11, 8], [10, 8], [0, 9], [1, 9], [11, 9], [10, 9], [9, 9], [1, 10], [10, 10], [0, 10], [9, 10], [11, 10], [10, 11], [9, 11], [8, 11], [11, 11], [1, 11], [2, 11], [0, 11], [0, 12], [1, 12], [10, 12], [9, 12], [2, 12], [8, 12], [3, 12], [7, 12], [2, 13], [6, 13], [3, 13], [4, 13], [1, 13], [8, 13], [0, 13], [9, 13], [7, 13], [5, 13], [6, 14], [1, 14], [0, 14], [7, 14], [2, 14], [8, 14], [4, 14], [3, 14], [5, 14], [6, 15], [2, 15], [0, 15], [1, 15], [5, 15], [3, 15], [4, 15]]
[]
[[14, 16], [15, 16], [16, 16], [18, 17], [17, 17], [15, 17], [16, 17], [14, 17], [18, 18], [19, 18], [14, 18], [13, 18], [19, 19], [18, 19], [20, 19], [13, 19], [14, 19], [19, 20], [18, 20], [14, 20], [18, 21], [19, 21], [17, 21], [15, 21], [16, 21], [14, 21], [15, 22], [17, 22], [18, 22], [16, 22], [14, 22]]
[[0, 21], [2, 21], [1, 21], [3, 22], [2, 22], [3, 23], [3, 24], [3, 25], [3, 26], [4, 26], [4, 27], [3, 27], [4, 28], [3, 28], [3, 29], [4, 29], [3, 30], [4, 30], [3, 31], [4, 31]]
[[25, 25], [29, 25], [26, 25], [28, 25], [27, 25], [25, 26], [29, 26], [28, 26], [26, 26], [27, 26], [27, 27], [25, 27], [26, 27], [26, 28], [25, 28], [26, 29], [25, 29], [25, 30], [25, 31]]

Answer 2

另一种迭代绘制算法实现，带有用于矢量探索的数组和用于选择的集合。

around =array([[[ 0,  1]],[[-1,  0]],[[ 1,  0]],[[ 0, -1]]])

def grow(seed,color):
    filled=set()
    current = set(tuple(x) for x in seed)
    while current :
        seed=np.vstack(current)
        x,y = (around+seed).reshape(-1,2).T
        np.clip(x,0,m.shape[0]-1,x)
        np.clip(y,0,m.shape[1]-1,y)
        good = (m[x,y]==color)
        win = np.vstack((x[good],y[good])).T
        front=set(tuple(x) for x in win)           
        current = front - filled
        filled |= current
    return np.vstack(filled) if filled else None

mout=m
seed=(vstack(np.where(m==1)).T)[:,None]
areas=dict()
n=4    

for color in (0,2,0,3):
     next=[ grow(s,color) for s in seed]
     areas[n]=next
     st=np.vstack(s for s in next if not s is None)  
     x,y=st.T
     mout[x,y] = n
     n +=1
     seed = [ x if x is not None else y for (x,y) in zip(next,seed) ]

imshow(mout)

对于 :

编辑

纯集解决方案，在此示例中更简单、更快速：

def grows(current,color,m):
    ra,rb=m.shape 
    filled=set()
    while current :
        next0={(a-1,b) for (a,b) in current if a>0}\
        | {(a,b-1) for (a,b) in current if b>0}\
        | {(a+1,b) for (a,b) in current if a<ra-1}\
        | {(a,b+1) for (a,b) in current if b<rb-1}        
        next = { p for p in next0 if m[p]==color}           
        current = next - filled
        filled |= current
    return filled

seed2=[set([p]) for p in zip(*np.where(m==1))]

def m2(seed,m):
    mout=m.copy()
    areas=dict()
    for i,color in enumerate((0,2,0,3)):
        next = [grows(s,color,mout) for s in seed]
        areas[i]=next
        for s in next :
            for p in s: 
                mout[p] = 4+i
        seed=[x or y for x,y in zip(next,seed)]
    return mout,areas 

mout,areas = m2(seed2,m)
imshow(mout)

在每个点的 numpy 矩阵中获取已知边界内的所有坐标点

Get all coordinates points within known boundaries in a numpy matrix for each dot

python

arrays

numpy

flood-fill