pythonarraysnumpyflood-fill
Get all coordinates points within known boundaries in a numpy matrix for each dot
Given the following numpy matrix
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]]
)
Which can be presented visually in a picture like this:
Where the red dots are numbered from left to right and can be identified in the matrix using the following function. Thanks to @DanielF in this answer
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]]
)
Two questions:
- Question 1: How can we identify all the white points coordinates (marked with
0) within the green boundaries (marked with2) which are located with red dots (marked with1) ? - Question 2: How can we identify all the white points coordinates (marked with
0) between black boundaries (marked with3) and the green boundaries (marked with2) which are located with red dots (marked with1) ?
I am looking for this result for this example matrix:
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]],
]
)
A few assumptions:
- The matrix shape can vary. It is not a fixed size.
- The number of red dots varies from matrix to matrix. But there is always at least one red dot in the matrix.¨
Solution
Question 1 Solution using a recursive floodfill algorithm:
See the floodfill algorithm in this JavaScript demonstration I made. GitHub Source.
I created a floodfill function first that works just like a paint program i.e. when given a point in an enclosed region, will fill in that region up to the border with a colour.
Then, all that needed to be done was to go through each red pixel (value 1) and floodfill up to green pixels (value 2) with the colour of what index red dot we are on (so that we can get the regions separately later).
Then, we simply use a version of your red_dots program that I modified to be a bit more generalised to get the result of all the coordinates of the white pixels.
This last step is done in a one-liner. It converts everything to a big list where each sub-list contains coordinates of a region of white pixels.
Note how we must end with a list at the end as this is not a rectangular shape so cannot use a numpy array (unless we use dtype=object).
Anyway, here is the code:
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))]
which creates the regions list as:
[[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]]
And to just visualise what the filled regions in np_matrix looks like, here is a screenshot from a matplotlib plot:
Question 2 Solution
The logic remains the same for this second section, just we have to do things in the right order. The way I would go about doing this would be to floodfill to the black borders with one colour and then subtract the white regions and green borders from this.
So, we need to work with a separate np_matrix as to not interfere with the first one. A copy can be made using np.copy.
We then need to fill in to the black border from the red dots and then from this filled in region, subtract all the coordinates that are in the white region or are green.
So, using the same functions from above, here is the code:
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]
which creates both lists, white_regions is the same as above and black_regions is:
[[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]]