Geek Answers Handbook

How to find neighbors of a 2d list in python?

I have a 2D list of 1 and 0:

Boundaries = [
[0,0,0,0,0],
[0,1,1,1,0],
[0,1,1,1,1],
[0,1,1,1,0],
[0,0,1,0,0]]

I need to check this list to see if there is 1 surrounded by 8 other 1s (for example, middle 1 on this list). If in environment 1 there is 1 environment, then it should be replaced with 0, so after starting the program the list above will return something like this:

[
[0,0,0,0,0],
[0,1,1,1,0],
[0,1,0,1,1],
[0,1,1,1,0],
[0,0,1,0,0]]

I am trying to use only one parameter (matrix 1 and 0). For some reason, this is an incredibly difficult thing to wrap your head around. So far, my code looks something like this:

def tempBoundaries(matrixC):
    for i in matrixC:
        for j in i:
            if j == 1:
                try:
                    if matrixC[i-1]==1 or matrixC[i+1]==1:
                     .......

This is a real fight for any reason, and I seem unable to figure out what to do, any advice or help would be greatly appreciated! Thank.

+4
source share
6

scipy, -

import numpy

boundaries = numpy.array([
                         [0,0,0,0,0],
                         [0,1,1,1,0],
                         [0,1,1,1,1],
                         [0,1,1,1,0],
                         [0,0,1,0,0]])

counts = scipy.signal.convolve2d(boundaries, numpy.ones((3,3)), mode='same')

# which gives you a matrix with counts of the number of 1s around each point
array([[ 1.,  2.,  3.,  2.,  1.],
       [ 2.,  4.,  6.,  5.,  3.],
       [ 3.,  6.,  9.,  7.,  4.],
       [ 2.,  5.,  7.,  6.,  3.],
       [ 1.,  3.,  4.,  3.,  1.]])

 # so then you just find the points where it == 9
 counts == 9
 array([[False, False, False, False, False],
        [False, False, False, False, False],
        [False, False,  True, False, False],
        [False, False, False, False, False],
        [False, False, False, False, False]], dtype=bool)

 # so you can update those positions
 boundaries[counts == 9] = 0

, :

boundaries = numpy.array(Boundaries)
counts = scipy.signal.convolve2d(boundaries, numpy.ones((3,3)), mode='same')
boundaries[counts == 9] = 0
+10

no numpy , , python.

. Hough Transform, (http://en.wikipedia.org/wiki/Hough_transform). , , , . 1 .

, . , , , , (-1, 0) , .

, . ( 8 ). , , 1 , , ( , ).

import collections
import itertools


def neighbours_of(i, j):
    """Positions of neighbours (includes out of bounds but excludes cell itself)."""
    neighbours = list(itertools.product(range(i-1, i+2), range(j-1, j+2)))
    neighbours.remove((i, j))
    return neighbours


def find_surrounded(grid):
    """List of x,y positions in grid where the cell is surrounded by 1s."""

    votes = collections.defaultdict(int)

    for i, x in enumerate(grid):
        for j, y in enumerate(x):
            # we don't get to vote if not ...
            if y == 0:
                continue

            # vote for everyone in the 3x3 square around us
            for a, b in neighbours_of(i, j):
                votes[(a, b)] += 1

    # now the things we want to change are those that got 8 votes
    surrounded_positions = [pos for pos, count in votes.items() if count == 8]

    return surrounded_positions

def change_when_cell_type_surrounded(grid, cell_type):
    """Update grid inline to flip bits of cells of cell_type that are surrounded."""

    # we'll flip to the opposite of what we're looking for
    change_to = 1 - cell_type

    surrounded = find_surrounded(grid)    

    for i, j in surrounded:
        if grid[i][j] == cell_type:
            grid[i][j] = change_to


grid = [[0,0,0,0,0],
        [0,1,1,1,0],
        [0,1,1,1,1],
        [0,1,1,1,0],
        [0,0,1,0,0]]

change_when_cell_type_surrounded(grid, 1)
change_when_cell_type_surrounded(grid, 0)
+3

, , . , , :

directions = [(-1, -1), (0, -1), ...]
def check_neighbors(m, x, y):
    for direction in directions:
        dx, dy = direction
        # You should check here that (x+dx, y+dx) 
        # is still inside the matrix
        if ...:
            continue
        if matrix[x+dx][y+dy] == 0:
            return False
    return True

- . , range .

# Big assumption: all sublists have the same length
for x in range(len(matrixC)):
    for y in range(len(matrixC[0])):
        if check_neighbors(matrixC, x, y):
            # Do what you want here
            ...
+2

:

Boundaries = [
[0,0,0,0,0],
[0,1,1,1,0],
[0,1,1,1,1],
[0,1,1,1,0],
[0,0,1,0,0]]

tochange = []
for i in xrange(len(Boundaries)-3):
    for j in xrange(len(Boundaries)-3):
        for k in xrange(3):
            for l in xrange(3):
                if not Boundaries[i+k][j+k]:
                    break
            else:
                continue
            break
        else:
            tochange.append((i+1, j+1))

for i, j in tochange:
    Boundaries[i][j] = 0
+1

you can use numpy

from numpy import ones
from scipy.signal import convolve2d

kernel = ones((3, 3))
#you create a matrix like this
#1 1 1
#1 1 1
#1 1 1

image = array(Boundaries)
#your boundaries were converted to a bidimensional numpy array

convolved = convolve2d(image, kernel, mode="same")
#you will have an image like this:
#[
#    [1,2,3,2,1],
#    [2,4,6,4,3],
#    [3,6,9,7,4],
#    [2,4,6,4,3],
#    [1,2,3,2,1]
#]

then you should change the images accordingly:

for (x,y), value in numpy.ndenumerate(a):
    image[x, y] = image[x, y] if convolved[x, y] < 9 else 0

disclaimer : this code does not kill 1s within bounds. You must modify it accordingly.

0
source

No numpy

Edit

I think this is the best solution because it interrupts the inner loop as soon as the neighbor is zero

def zero_one(input2d, r, c):
    for rr in (r-1, r, r+1):
        for cc in (c-1, c, c+1):
            if input2d[rr][cc] == 0 : return 1
    return 0

Boundaries = [[0,0,0,0,0],
              [0,1,1,1,0],
              [0,1,1,1,1],
              [0,1,1,1,0],
              [0,0,1,0,0]]

rows = 5
cols = 5
Output = []

for r in range(rows):
    Output.append([])
    for c in range(cols):
        if (r==0 or r==rows-1) or (c==0 or c==cols-1):
            Output[r].append(Boundaries[r][c])
        elif Boundaries[r][c] == 0:
            Output[r].append(0)
        else:
            Output[r].append(zero_one(Boundaries, r, c))

for line in Output:
    print line

execution of the above code gives

[0, 0, 0, 0, 0]
[0, 1, 1, 1, 0]
[0, 1, 0, 1, 1]
[0, 1, 1, 1, 0]
[0, 0, 1, 0, 0]

My previous code after

End of editing

In [15]: Boundaries = [
[0,0,0,0,0],
[0,1,1,1,0],
[0,1,1,1,1],
[0,1,1,1,0],
[0,0,1,0,0]]

In [16]: Output = [
[0,0,0,0,0],
[0,1,1,1,0],
[0,1,1,1,1],
[0,1,1,1,0],
[0,0,1,0,0]]

In [17]: for i in (1, 2, 3):
    for j in (1,2,3):
        s = 0
        for m in (i-1, i, i+1):
            for n in (j-1, j, j+1):
                s = s+Boundaries[n][m]
        if s == 9 : Output[j][i] = 0
   ....:         

In [18]: Output
Out[18]: 
[[0, 0, 0, 0, 0],
 [0, 1, 1, 1, 0],
 [0, 1, 0, 1, 1],
 [0, 1, 1, 1, 0],
 [0, 0, 1, 0, 0]]

In [19]:
0
source

More articles:


All Articles