calculate coordinates of blocks in diagonal block matrix

Question

I have a diagonal block matrix and I want the coordinates (row, column) of each block

a = np.zeros((25,18), dtype=int)    
a[2:8,:6]=1

a[8:13,6:12]=1

a[13:15,12:14]=1

a[15:20,14:]=1

and the output

 [(2, 0), (8, 6), (13, 12), (15, 14)]

Thanks!

Can you give some sample input and expected output? See for example this question http://stackoverflow.com/q/29447164/553404 — YXD, Apr 04 '15 at 21:55

Greg Edelston · Answer 1 · 2015-04-05T02:14:58.003

I'll assume that your matrix is indeed full of booleans, like in your picture.

Each block is perfectly square, and thus can be defined by its starting coordinates and its side-length. Note also that the starting coordinates will always lie along the diagonal of the matrix, so the row and column are equal.

If you look at the picture, it is plain to see that at the start of every block, the cell immediately above (or to the left) is False. Thus we can create a list of blocks, [(coordinate,length),...], as follows:

# Find the coordinates where each block starts
starts = []
for i in range(len(myMatrix)):
    if i==0:
        starts.append(i)
    elif not myMatrix[i,i-1]: # i.e., if the cell to the left is False
        starts.append(i)
# Get the length of each block
blocks = []
for i in range(len(starts)):
    thisStart = starts[i]
    if i == len(starts)-1:
        nextStart = len(myMatrix)
    else:
        nextStart = starts[i+1]
    length = nextStart - thisStart
    blocks.append((thisStart, length))

Greg, the coordinates for the starts work fine, but the second part have a problem. Thanks! Traceback (most recent call last): File "", line 8, in TypeError: unsupported operand type(s) for -: 'int' and 'list' — Daniel Garavito, Apr 04 '15 at 22:49
Try it again -- I've fixed an error in the last line. If that wasn't it, can you clarify which line you were finding the error? — Greg Edelston, Apr 05 '15 at 02:16

score 0 · Accepted Answer · answered Apr 05 '15 at 01:52

If, as in your example, every column contains one block or other, you can get the coordinates of each block by scanning for the first non-zero entry in each column and keeping track of the corresponding rows:

In [1]: import numpy as np
In [2]: a = np.zeros((25,18), dtype=int)    
In [3]: a[2:8,:6]=1
In [4]: a[8:13,6:12]=1
In [5]: a[13:15,12:14]=1
In [6]: a[15:20,14:]=1
In [7]: rows = set()
In [8]: blocks = []
In [9]: for col in range(a.shape[1]):
            row = np.argmax(a[:,col])
            if row not in rows:
                rows.add(row)
                blocks.append((row, col))
....:         

In [10]: blocks
Out[10]: [(2, 0), (8, 6), (13, 12), (15, 14)]

calculate coordinates of blocks in diagonal block matrix

2 Answers2