CODEWITHSUNDEEP
pythonnumpyrandom
A.M.
A.M.

Reputation: 1797

Random sampling of non-adjacent cells in a pixel grid

Suppose that we have a n*n grid. We would like to choose k << n random cells of this grid which are not adjacent. If we simulate this grid with a 2D Numpy array containing 0 and 1, what is the most efficient way to do this in Numpy/Python?

Valid Example:

enter image description here

Non-valid Example:

enter image description here

Upvotes: 3

Views: 870

Answers (2)

YXD
YXD

Reputation: 32511

Here's a straightforward implementation of the rejection sampling. There may be a faster way to do the adjacency check than the query_pairs thing (which in this case also will check for collisions), since you only want to test if there is at least one pair within this distance threshold.

import numpy as np
from scipy.spatial import cKDTree as kdtree

n = 100
k = 50

valid = False

while not valid:
    # generate k grid indices
    coords_flat = np.random.random_integers(0, n ** 2 - 1, size=k)
    coords = np.unravel_index(coords_flat, dims=(n, n))
    # test there are no adjacent cells
    transposed = np.transpose(coords)
    valid = len(kdtree(transposed).query_pairs(1.0)) == 0

print(coords)

Taking a look at the results:

import matplotlib.pyplot as plt
grid = np.zeros((n, n), dtype=np.bool)
grid[coords] = True
plt.imshow(grid)
plt.savefig('result.png')

enter image description here

Upvotes: 4

Geeocode
Geeocode

Reputation: 5797

I saw, that it was an accepted answer already, but it was a challenging task, so I solved as follows and I enjoy it, thus I gave an upvote to the question :):

import numpy as np

xy = []

x = np.random.randint(0,5)
y = np.random.randint(0,5)

xy.append((x,y))

while True:

    x = np.random.randint(0,5)
    y = np.random.randint(0,5)

    for ii,i in enumerate(xy):    
        if x in [i[0]-1, i[0], i[0]+1]:
            if x == i[0]:
                if y in [i[1]-1, i[1], i[1]+1]:
                    break    
                else:
                    if ii == len(xy) - 1:
                        xy.append((x,y))
                        break
            elif y == i[1]:
                break
        elif ii == len(xy) - 1:
            xy.append((x,y))
            break

    if len(xy) == 3:
        break

for cords in xy:
    print cords

sq =np.zeros((5,5))

for cords in xy:
    sq[cords] = 1

print sq

Output:

(1, 0)
(4, 4)
(4, 1)
[[ 0.  0.  0.  0.  0.]
 [ 1.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.]
 [ 0.  1.  0.  0.  1.]]

It always provides a random combination of non-adjacent cells. Enjoy it! :)

Upvotes: 4

Related Questions