rle for finding rectangles in matrix

Question

I'm following this approach to find rectangles of 1's in a (0,1) matrix

Find 5 consecutive numbers >= 3 for each row of a matrix

but there's a problem when I try to find 1x4 rectangles (1 row and 4 columns) like in this matrix

m <- matrix(c(0,1,1,1,1,0,0,0,1,0,1,0,0,1,0,1,1,1,1,0,0,1,1,1,1,1,1,1,1,0), nrow = 6, ncol = 5, byrow = TRUE)

There are four rectangles: 1st row, 4th row, 5th row and 6th row

   [,1] [,2] [,3] [,4] [,5]
[1,]    0    1    1    1    1
[2,]    0    0    0    1    0
[3,]    1    0    0    1    0
[4,]    1    1    1    1    0
[5,]    0    1    1    1    1
[6,]    1    1    1    1    0

when I run the code for this case I get the 4 results, but two of them (4th and 6th row) both results start at first column but in the result I get as starting column the 5th and ending column the 8th when the matrix is 6x5 and can't find out which is the problem.

b<-m

for (j in 1:5){
cont<-1
 for (i in 6:1) {
 if (m[i,j]==0){
cont<-1
b[i,j]<-NA}
 else {b[i,j]<-cont
cont<-cont+1}
}
}


mdat<-b

apply(mdat, 1, function(x) {
  r <- rle(x >= 1)
  w <- which(!is.na(r$values) & r$values & r$lengths >=4)
  if (length(w) > 0) {
    before <- sum(r$lengths[1:(w[1]-1)])
    c(before+1,before+ r$lengths[w[1]])
  } else
    NULL
})

[[1]]
[1] 2 5

[[2]]
NULL

[[3]]
NULL

[[4]]
[1] 5 8

[[5]]
[1] 2 5

[[6]]
[1] 5 8

What do you define as "rectangles"? You mean 4 consecutive 1's in a single row? — David Arenburg

digEmAll digEmAll · Accepted Answer · 2014-08-31T14:54:07

You need to change the calculation of before variable since it does not work if the row starts with the sequence of 1's :

apply(mdat, 1, function(x) {
  r <- rle(x >= 1)
  w <- which(!is.na(r$values) & r$values & r$lengths >=4)
  if (length(w) > 0) {
    before <- sum(r$lengths[1:w[1]]) - r$lengths[w[1]]
    c(before+1,before+r$lengths[w[1]])
  } else
    NULL
})

Problem was the following line :

before <- sum(r$lengths[1:(w[1]-1)])

that works properly only if the sequence of ones is not at the first position (i.e. w > 1).

BTW, note that your code only consider the first sequence in the row, ignoring other sequences (if present).
e.g. supposing to have one matrix row = c(0,1,1,1,1,0,1,1,1,1), it will return only c(2,5) and not c(2,5), c(7,10)

If you want something returning all the sequences, you can use this code :

apply(mdat, 1, function(x) {
  r <- rle(x >= 1)
  w <- which(!is.na(r$values) & r$values & r$lengths >=4)
  if (length(w) > 0) {
    lapply(w,FUN=function(w1){ before <- sum(r$lengths[1:w1]) - r$lengths[w1];
                               c(before+1,before+r$lengths[w1]) })
  } else
    NULL
})

N.B. it returns a list where each element is a list containing the pairs

rle for finding rectangles in matrix

1 Answers