CODEWITHSUNDEEP
matlab
slayton
slayton

Reputation: 20319

Calculating overlap in Mx2 and Nx2 matrices

I have two matrices A and B, both contain a list of event start and stop times:

A(i,1) = onset time of event i
A(i,2) = offset time of event i
B(j,1) = onset of event j
...

My goal is to get two lists of indecies aIdx and bIdx such that A(aIdx,:) and B(bIdx,:) contain the sets of events that are overlapping.

I've been scratching my head all day trying to figure this one out. Is there a quick, easy, matlaby way to do this?

I can do it using for loops but this seems kind of hacky for matlab:

aIdx = [];
bIdx = []
for i=1:size(A,1)
    for j=i:size(B,1)
        if overlap(A(i,:), B(j,:)) % overlap is defined elsewhere
            aIdx(end+1) = i;
            bIdx(end+1) = j;
        end
    end
end

Upvotes: 2

Views: 871

Answers (4)

3lectrologos
3lectrologos

Reputation: 9662

Here's a zero loop solution:

overlap = @(x, y)y(:, 1) < x(:, 2) & y(:, 2) > x(:, 1)
[tmp1, tmp2] = meshgrid(1:size(A, 1), 1:size(B, 1));
M = reshape(overlap(A(tmp1, :), B(tmp2, :)), size(B, 1), [])';
[aIdx, bIdx] = find(M);

Upvotes: 3

Abhinav
Abhinav

Reputation: 1972

Completely vectorized code without repmat or reshape (hopefully faster too). I have assumed that the function "overlap" can give a vector of 1's and 0's if complete pairs of A(req_indices,:) and B(req_indices,:) are fed to it. If overlap can return a vector output, then the vectorization can be performed as given below.

Let rows in A matrix be Ra and Rows in B matrix be Rb, 

AA=1:Ra;
AAA=AA(ones(Rb,1),:);
AAAA=AAA(:); % all indices of A arranged in desired format, i.e. [11...1,22..2,33...3, ...., RaRa...Ra]'

BB=(1:Rb)';
BBB=BB(:,ones(Ra,1)); 
BBBB=BBB(:);% all indices of B arranged in desired format, i.e. [123...Rb, 123...Rb,....,123...Rb]'

% Use overlap function
Result_vector = overlap(A(AAAA,:), B(BBBB,:));
Result_vector_without_zeros = find(Result_vector);
aIdx = AAAA(Results_vector_without_zeros);
bIdx = BBBB(Results_vector_without_zeros);

DISADVANTAGE : TOO MUCH RAM CONSUMPTION FOR LARGER MATRICES

Upvotes: 0

ely
ely

Reputation: 77454

overlap_matrix = zeros(size(A,1),size(B,1))

for jj = 1:size(B,1)
    overlap_matrix(:,jj) = (A(:,1) <= B(jj,1)).*(B(jj,1) <= A(:,2));       
end

[r,c] = find(overlap_matrix)
% Now A(r(i),:) overlaps with B(c(i),:)

% Modify the above conditional if you want to also check
% whether events in A start in-between the events in B
% as I am only checking the first half of the conditional
% for simplicity.

Upvotes: 1

yuk
yuk

Reputation: 19880

You can do it with one loop:

aIdx = false(size(A,1),1);
bIdx = false(size(B,1),1);
for k = 1:size(B,1)
    ai = ( A(:,1) >= B(k,1) & A(:,1) <= B(k,2) ) | ...
           ( A(:,2) >= B(k,1) & A(:,2) <= B(k,2) );
    if any(ai), bIdx(k) = true; end
    aIdx = aIdx | ai;
end

There is a way to create a vectorized algorithm. (I wrote a similar function before, but cannot find it right now.) A simply workflow is to (1) combine both matrices, (2) create an index to indicate source of each event, (3) create a matrix indicating start and stop positions, (4) vectorized and sort, (5) find overlaps with diff, cumsum, or combination.

Upvotes: 1

Related Questions