How to find indices of a rectangular region inside big matrix? | Efficiently

How can indices of elements belong to a rectangular region can be found?

A = [4     4     4     4     4     4     4
     4     1     1     1     1     3     0
     4     1     3     3     1     3     0
     4     1     3     3     1     3     0
     4     1     1     1     1     3     0
     4     4     4     4     4     4     4];

Input: Matrix's size[height, width] , [Row_start Row_end], [Col_start Col_end]

Output: [21 22 23 27 28 29 33 34 35]

Why efficiently : to do same for multiple combinations of rows & columns

Thank you

[Caglar]

How is [3 1 3; 3 1 3; 1 1 3] is a 'rectangle'?

[JAI PRAKASH]

I mentioned rectangle instead of square to generalise, considering other row & col combinations.

e.g. rectangle for

[Row_start Row_end], [Col_start Col_end] = [2 3], [2 6]

[Caglar]

I am not sure If I understood what you are asking for. If you want to get a part of a matrix you can do it like A(3:5,4:6) .

[JAI PRAKASH]

Sorry if I am not clear in my question.

I want linear indices of all the elements present in rectangular region.

e.g

Answer 1

[Bruno Luong]

recidx = (Row_start:Row_End)' + height*(Col_start-1:Col_end-1)

[JAI PRAKASH]

Thanks, very synthesized.

[JAI PRAKASH]

Actually I need to input same size column vectors of Row_start, Row_End, Col_start and Col_end, to get output for all combinations.

For this above 'recidx' should be 1-D for 1 combination. And 2D for more than 1 combination. Obviously #elements for each combination would be different, to maintain 2-D matrix dimension '0' can be used.

Can you help me with this!!

Thanks

[Bruno Luong]

Adapt for multi-rectangles as requested:

sz = (Row_End-Row_start+1).*(Col_end-Col_start+1);
padsz = max(sz) - sz;
idxfun = @(r1,r2,c1,c2,p) [reshape((r1:r2)'+height*(c1-1:c2-1),1,[]), ...
                           zeros(1,p)];
idxcell = arrayfun(idxfun, Row_start, Row_End, Col_start, Col_end, padsz, 'unif', 0);
RecIdx = cat(1,idxcell{:})

[JAI PRAKASH]

Thanks @Bruno Luong

This is what was required.

Thanks a lot

[JAI PRAKASH]

Hi @Bruno

Do you have some idea for below question also.

How can already used elements be eliminated one by one in 2D matrix while moving upwards? | Efficiently

Which is nothing but continuation of the problem, that you solved just now.

[Bruno Luong]

James's solution is very well. I doubt I can do better.

Answer 2

[Geoffrey Schivre]

Hello,

I'm not sure if it's efficient enough but try :

p = nchoosek([Row_start:Row_end,Col_start:Col_end],2);
idx = unique(sub2ind(size(A),p(:,1),p(:,2)));

Geoffrey

[Geoffrey Schivre]

To find indices of a 10 by 20 bloc in a 1e6 by 1e6 matrix takes less than 10ms :

tic
N = 1e6;
n1 = randi([1,N],1,1);
n2 = randi([1,N],1,1);
p = nchoosek([n1:(n1+9),n2:(n2+19)],2);
idx = unique(sub2ind([N,N],p(:,1),p(:,2)));
toc
Elapsed time is 0.008410 seconds.

The time scale up only with the size of the rectangle you are looking for.

[JAI PRAKASH]

Thanks @Geoffrey Schivre

This code merges every combination's output. I prefer a link between input & output.

Thanks

[Geoffrey Schivre]

When you are looking for big rectangle use :

p1 = nchoosek([Row_start:Col_end],2);
p2 = nchoosek([Col_start:Row_end],2);
p3 = intersect([Row_start:Col_end],[Col_start:Row_end]);
p = [p1;p2;[p3',p3']];
idx = sub2ind(size(A),p(:,1),p(:,2));

This methode is less efficient on small rectangle but more efficient on large one due to the use of nchoosek on smaller vectors :

small rectangle (100 by 100) :

tic
N = 10000;
n1 = 10;
n2 = 10;
s1 = 99;
s2 = 99;
p = nchoosek([n1:(n1+s1),n2:(n2+s2)],2);
idx = unique(sub2ind([N,N],p(:,1),p(:,2)));
toc
Elapsed time is 0.016082 seconds.
tic
N = 10000;
n1 = 10;
n2 = 10;
s1 = 99;
s2 = 99;
p1 = nchoosek([n1:(n2+s2)],2);
p2 = nchoosek([n2:(n1+s1)],2);
p3 = intersect([n1:(n2+s2)],[n2:(n1+s1)]);
p = [p1;p2;[p3',p3']];
idx = sub2ind([N,N],p(:,1),p(:,2));
toc
Elapsed time is 0.020043 seconds.

large rectangle (1000 by 1000) :

tic
N = 10000;
n1 = 10;
n2 = 10;
s1 = 999;
s2 = 999;
p = nchoosek([n1:(n1+s1),n2:(n2+s2)],2);
idx = unique(sub2ind([N,N],p(:,1),p(:,2)));
toc
Elapsed time is 21.936548 seconds.
tic
N = 10000;
n1 = 10;
n2 = 10;
s1 = 999;
s2 = 999;
p1 = nchoosek([n1:(n2+s2)],2);
p2 = nchoosek([n2:(n1+s1)],2);
p3 = intersect([n1:(n2+s2)],[n2:(n1+s1)]);
p = [p1;p2;[p3',p3']];
idx = sub2ind([N,N],p(:,1),p(:,2));
toc
Elapsed time is 5.138268 seconds.

[Geoffrey Schivre]

Sorry, I didn't refresh this page so I didn't see that your question was answered. I'm glad you find what you ask for !

[JAI PRAKASH]

Ya, But I learn interesting things from your comments.

'nchoosek' is new to me

Thanks

Answer 3

[Caglar]

function result = stack (A,row_start,row_end,col_start,col_end)
% A = [4     4     4     4     4     4     4
%      4     1     1     1     1     3     0
%      4     1     3     3     1     3     0
%      4     1     3     3     1     3     0
%      4     1     1     1     1     3     0
%      4     4     4     4     4     4     4];
%  row_start=3; col_start=4;
%  row_end=5; col_end=6;

height=(size(A,1));
result=(row_start:row_end)+(height)*((col_start:col_end)'-1);
result=transpose(result); result=result(:);
end