在一个numpy矩阵中得到每个d的已知边界内的所有坐标点

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在这个answer

^{pr2}$

两个问题：

• 问题1：如何识别所有白点坐标（用 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解决方案：

请参阅我制作的这个JavaScript demonstration中的泛洪填充算法。GitHub Source。

我首先创建了一个泛光填充函数，它的工作原理与绘制程序类似，即当在封闭区域中给定一个点时，将用颜色填充该区域直至边界。在

然后，需要做的就是遍历每个红色像素（值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列表，如下所示：

^{pr2}$

---

为了直观地显示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]

这将创建两个列表，白色区域与上面相同，黑色区域为：

[[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)     

用于：

编辑

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

^{pr2}$