Python Forum
Neighbours in an array
Thread Rating:
  • 3 Vote(s) - 2 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Neighbours in an array
#1
Hi everyone,

I've got the following problem: 

Example: 
If the original Input is:


[[0 0 0 0 0 0 0 1]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 1 1 1 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]]
The result should be:

[[0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 1 1]
[1 2 3 2 1 0 0 0]
[1 1 2 1 1 0 0 0]
[1 2 3 2 1 0 0 0]
[0 0 0 0 0 0 0 0]]
I started as following:



from numpy import zeros

inp = zeros(shape=(6,8),dtype=int)
inp[0,7]=1
inp[3,1:4] = 1

inp_new = 0*inp
print(inp)

P = inp.shape[0]
Q = inp.shape[1]

print(P, Q)

for p in range(1,P-1):
    for q in range(1, Q-1):
        inp_new[p,q] = inp[p+1, q]+inp[p-1, q]+ inp[p, q+1] + inp[p, q-1]+inp[p+1,q+1]+inp[p+1,q- 1]+inp[p+1,q-1]+inp[p-1,q- 1]
But something is wrong, especially with the first and the last columns and rows. 

Thanks for any help! :)
Reply
#2
So, it sounds like we are on the path to implementing Conway.  Firstly, you may be being instructed to loop through arrays like this, but this isn't the best way to do it.  In Conway you often have more empty space than not (especially if you consider a simulation on an infinite grid) so iterating through all those cells is a waste of time.

That aside, let's do it your way and then we can talk about more efficient ways if that interests you (or not).

Let's be programmers.  Don't try to write each neighbor out; create a sequence and iterate.  Also, be aware that negative indexes have meaning in python but in this case you probably don't want to consider wrapping so let's ignore them (same for indexes that are too high).
import numpy as np

inp = np.zeros((6,8), dtype=int)
inp_new = inp.copy()
inp[0,7] = 1
inp[3,1:4] = 1
 
P,Q = inp.shape

ADJACENTS = {(-1, 1), (0, 1), (1, 1), (-1, 0),
             (1, 0), (-1, -1), (0,-1), (1,-1)}
 
for y,row in enumerate(inp):
    for x,val in enumerate(row):
        for dy, dx in ADJACENTS:
            if 0 <= y+dy < P and 0 <= x+dx < Q:
                inp_new[y,x] += inp[y+dy,x+dx]

print(inp_new)
Output:
[[0 0 0 0 0 0 1 0]  [0 0 0 0 0 0 1 1]  [1 2 3 2 1 0 0 0]  [1 1 2 1 1 0 0 0]  [1 2 3 2 1 0 0 0]  [0 0 0 0 0 0 0 0]]
Reply
#3
Awwww very good idea with the adjacents!! :) 
So you define the possible directions of the neighbours (one entry up, one beside etc...) 

You mentioned a more efficient way. Well, I'm very happy with your proposition because I understand it :) 
But of course, I'd be interested in a more efficient way to solve this question :)
Reply
#4
Quote:But of course, I'd be interested in a more efficient way to solve this question
So, you have two possible solutions.  One works great for the mentioned infinite scenario.

In that method you simply keep sets of the living cells.
You iterate through the living cells and for every living cell add 1 to each neighbor cell in a dictionary.

Looks like this:
neighbors = {}
for x,y in current:
    for i,j in ADJACENTS:
        check = (x+i, y+j)
        neighbors[check] = neighbors.get(check, 0) + 1
Now you have a dictionary where keys are coordinates (x,y) and values are the number of neighbors that cell has.

Full implementation here:
https://github.com/Mekire/Conway-User-Interaction
with the key functions on these lines:
https://github.com/Mekire/Conway-User-In...fe.py#L127
https://github.com/Mekire/Conway-User-In...fe.py#L144
You will need to have pygame installed if you want to run it but it is a fully interactive example.

Now the next option, and one that better suits you using numpy arrays is something called convolution.  It looks complicated but basically you have a kernel that you smear across an entire array.  All of its values multiply against the area of the array it is over and the sum goes in the cell (basically exactly what you want).  It is very common in image and signal processing.  We want the sum of all surrounding values not including ourself so we use a kernel that looks like this:
[[1 1 1]
 [1 0 1]
 [1 1 1]]
Now we could implement convolution ourselves (and it would be horrible), but lucky for us it exists in signal and image libraries like opencv or scipy.

Your entire code becomes this:  
import numpy as np
from scipy import signal
 
inp = np.zeros((6,8), dtype=int)
inp_new = inp.copy()
inp[0,7] = 1
inp[3,1:4] = 1

kernel = np.ones((3,3), dtype=int)
kernel[1,1] = 0
new_inp = signal.convolve2d(inp, kernel, mode="same")
print(new_inp)
Again you will of course need to install scipy but as you are using numpy you should do that anyway.
Reply
#5
Wow in 3 lines :D

Perfect. Thanks a lot for your help and your inputs!
Reply
#6
Hi Mekire

I've got a little variation of the task: Change the first array at the positions indicated by the second array as follows: Replace the value by the maximum value of itself and its 4 closest neighbors. If there are less than 4 closest neighbors, take the maximum of the closest neighbors that are present.

So, if we have as input:
[[ 0 0 0 0 0 0 2 3] 
 [ 0 0 0 0 0 0 0 0] 
 [ 0 0 0 0 0 0 0 0] 
 [ 6 8 8 0 0 0 0 0] 
 [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]]
and the second array:
inp2=np.array([[0,5],[0,7],[2,1],[3,0]])

The result should be:
[[ 0 0 0 0 0 2 2 3] 
 [ 0 0 0 0 0 0 0 0] 
 [ 0 8 0 0 0 0 0 0] 
 [ 8 8 8 0 0 0 0 0] 
 [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]]
At the moment, I've got the following code. But I think that I misunderstood something :/

import numpy as np
inp1 = np.zeros(shape=(6,8),dtype=int)
inp1[0,6] = 2
inp1[0,7] = 3
inp1[3,0] = 6
inp1[3,1:3] = 8

inp2=np.array([[0,5],[0,4],[2,1],[3,0]])
inp_new=0*inp1
inp12 = inp1[inp2[:,0], inp2[:,1]]
P,Q = inp1.shape
ADJACENTS = [(0, 1), (-1, 0), (1, 0), (0,-1)]

for i in inp12:
    for y,row in enumerate(inp1):
        for x,val in enumerate(row):
            for dy, dx in ADJACENTS:
                if 0 <= y+dy < P and 0 <= x+dx < Q:
                    inp_new[y,x] = max((inp_new[y,x], inp1[y+dy,x+dx]))
print(inp_new)
Could you help me again? :)
Reply
#7
There is no reason to iterate over the whole array as we did previously.  You only need to check the points in the second input array.

Replace comments below with appropriate code:
for y, x in inp2:
    # set maximum to the current value 
    for dy, dx in ADJACENTS:
        if 0 <= y+dy < P and 0 <= x+dx < Q:
            # set maximum to adjacent value if higher than current maximum
    # set the location in the new array to the maximum
Reply
#8
Hi Mekire,

Hm, I didn't find a correct solution :/
How is it possible to iterate only through the second input array? 

Thanks for any help!
Reply
#9
My previous reply was basically the answer.  
for y, x in inp2:
    # set maximum to the current value 
    for dy, dx in ADJACENTS:
        if 0 <= y+dy < P and 0 <= x+dx < Q:
            # set maximum to adjacent value if higher than current maximum
    # set the location in the new array to the maximum
Just replace the lines.  You still index into inp1 with the coordinates (x, y, x+dx, y+dy).

Set the initial maximum to inp1[y,x]
Then on line four set maximum to the adjacent you are checking inp1[y+dy, x+dx] if that is higher than current maximum.
On line five set inp_new[y,x] to the maximum.
Reply
#10
But do you consider this condition in the code? :

"If there are less than 4 closest neighbors, take the maximum of the closest neighbors that are present."
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  How to find the accuracy vs number of neighbours for KNN vokoyo 3 3,108 Apr-10-2019, 03:46 AM
Last Post: scidam

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020