Holen Sie sich alle Koordinatenpunkte innerhalb bekannter Grenzen in einer numpy Matrix für jeden Punkt

Question

Angesichts der folgenden 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]] 
) 

, die visuell in einem Bild wie folgt dargestellt werden kann:

Wo die roten Punkte sind von links nach rechts nummeriert und können in der Matrix mit der folgenden Funktion identifiziert werden. Dank @DanielF in diesen 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]] 
)  

Zwei Fragen:

• Frage 1: Wie können wir alle weißen Punkte Koordinaten identifizieren (markiert mit 0) in den grünen Grenzen (markiert mit 2) die mit roten Punkten (markiert mit 1)?
• Frage 2: Wie können wir alle weißen Punkte identifizieren Koordinaten (mit markiert 0) zwischen schwarzen Grenzen (markiert mit 3) und den grünen Grenzen (markiert mit 2), die mit roten angeordnet sind Punkte (markiert mit 1)?

Ich suche für dieses Ergebnis für dieses Beispiel 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]], 
    ] 
) 

Einige Annahmen:

• Die Matrixform variieren kann. Es ist keine feste Größe.
• Die Anzahl der roten Punkte variiert von Matrix zu Matrix. Aber gibt es immer mindestens einen roten Punkt in der matrix.¨

Answer 1

Frage 1 Lösung unter Verwendung eines recursivefloodfillalgorithm:

die floodfillalgorithm Siehe in diesem JavaScript demonstration ich gemacht.

Ich habe eine floodfill Funktion ersten, der wie ein paint Programm funktioniert das heißt, wenn ein Punkt in einem geschlossenen Bereich gegeben, wird mit einer Farbe in diesem Bereich bis an die Grenze zu füllen.

Dann alles, was getan werden mußte, war durch jedes red (Pixel 1) zu gehen und überflutet fill bis zum green (Pixel 2) mit der Farbe, was red Punkt sind wir auf (so dass wir das bekommen Regionen getrennt später).

Dann verwenden wir einfach eine Version Ihres red_dots Programm, das ich ein bisschen mehr verallgemeinert zu bekommen das Ergebnis aller coordinates der white Pixel sein geändert.

Dieser letzte Schritt wird in einem one-liner alles getan, was zu einem großen list zu umwandeln, wo jeder sub-listcoordinates eines region von white enthält.

Beachten Sie, wie wir am Ende mit einem list am Ende enden müssen, da dies keine rechteckige Form ist, so kann kein numpy array sein (es sei denn, wir verwenden dtype=object).

, Auf jeden Fall hier ist der 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))] 

, die die regionslist wie schafft: es funktioniert nicht print wie diese

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

offensichtlich, wie es ein list ist, aber es ist einfacher zu sehen, so

---

Und nur zu visualisieren, was die filled in np_matrix aussieht, hier ist ein screenshot von einem matplotlib Ausgang:

---

Frage 2 Lösung

Die Logik bleibt das gleiche für In diesem zweiten Abschnitt müssen wir nur die Dinge in der richtigen Reihenfolge tun. Die Art und Weise, wie ich dies tun würde, wäre floodfill, um die black Grenzen mit einer Farbe und dann die whiteregions und green Grenzen davon abziehen.

Also müssen wir mit einem separaten np_matrix arbeiten, um nicht mit dem ersten zu stören. Eine Kopie kann mit np.copy erstellt werden.

Wir müssen dann auf die blackborder aus den red Punkte füllen und dann von diese in region gefüllt, subtrahieren alle Koordinaten, die im weißen Bereich sind oder green.

also die gleiche functions von oben mit, hier ist der 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] 

die sowohl lists schafft, white_regions ist die gleiche wie oben und black_regions ist:

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

wie vor Dies ist nicht der Fall, wie normalerweise eine list angezeigt wird, aber ist einfacher zu sehen

Answer 2

Eine weitere iterative Paint-Algorithmusimplementierung mit Arrays für die vektorielle Exploration und Sets zur Auswahl.

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)  

Für:

bearbeiten

Eine reine Satz Lösung, einfacher und schneller auf dieses Beispiel:

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)