find and index equal values in multidimensional matrix

Question

I am producing a three dimensional matrix with two rows(e.g. a 2x1000x10 matrix). These contain x- and y-coordinates for dot motion paths, where the first line contains the x-coordinates and the second line the y-coordinates. The number of columns (here: 1000) depends on the length of the motion paths. The number of levels in the third dimension depends on the number of dots (here: 10).

I want to know if some dots are going to overlap, i.e. if any x- and y-coordinates across the third dimension at the same time point t, i.e. any combination of (:, t, :), are identical. So the comparison will be within the matrix.

i = [1:size(matrix, 3)];
j = [1:size(matrix, 3)];
t = [1:size(matrix, 2)];

crash = any(coordinates(:, t, i)==coordinates(:, t, j))

would be trivial because i and j can be the same and thus say that the point is equal to itself.

Do you know how I can detect equal value combinations across matrix dimensions? How do I index them if they exist?

Answer 1

I think this does what you want. To find out if there's a crash:

t = bsxfun(@eq, coordinates, permute(coordinates, [1 2 4 3]));
crash = any(sum(any(all(t,1),2),4)>1,3);

We first use bsxfun to compute a 4D array (t) that tests for equality in the same coordinate (1st dim) and the same position along path (2nd dim), where the 3rd and 4th dims run over all pairs of dots. A crash occurs if both coordinates (all(,...,1)) are equal for any column (any(...,2)) in more than one "other" dot (sum(...,4)>1) for any "reference" dot (any(...,3)). We need to specify "more than one" because any dot is at least equal to itself (for a given position and coordinate).

Example:

>> coordinates = randi(9,2,5,4)
coordinates(:,:,1) =
     7     4     3     3     8
     7     1     4     2     4
coordinates(:,:,2) =
     8     7     8     4     8
     4     4     7     2     9
coordinates(:,:,3) =
     3     4     7     8     5
     7     8     2     9     8
coordinates(:,:,4) =
     6     2     7     8     5
     2     4     8     3     1

>> t = bsxfun(@eq, coordinates, permute(coordinates, [1 2 4 3]));
>> crash = any(sum(any(all(t,1),2),4)>1,3)
crash =
     0

>> coordinates(:,2,4) = coordinates(:,2,1) %// 4th dot equal to 1st dot in column 2
coordinates(:,:,1) =
     7     4     3     3     8
     7     1     4     2     4
coordinates(:,:,2) =
     8     7     8     4     8
     4     4     7     2     9
coordinates(:,:,3) =
     3     4     7     8     5
     7     8     2     9     8
coordinates(:,:,4) =
     6     4     7     8     5
     2     1     8     3     1

>> t = bsxfun(@eq, coordinates, permute(coordinates, [1 2 4 3]));
>> crash = any(sum(any(all(t,1),2),4)>1,3)
crash =
     1

---

To find the coordinates of the crash:

t = bsxfun(@eq, coordinates, permute(coordinates, [1 2 4 3]));
[m,n,p] = size(coordinates);
ii = find(squeeze(all(bsxfun(@times, t, ...
    bsxfun(@ne, reshape(1:p, 1,1,[]), reshape(1:p, 1,1,1,[]) )),1)));
[col, dot_ref, dot_oth] = ind2sub([n p p], ii);

In the latter example, this gives

col =
     2
     2
dot_ref =
     4
     1
dot_oth =
     1
     4

which tells you that the dot 4 equals dot 1 in column 2; and then of course that dot 1 equals dot 4 in column 2.

This computes the same t as above. It then multiplies by a logical mask along the third and fourth dimensions (bsxfun(@ne, reshape(1:p, 1,1,[]), reshape(1:p, 1,1,1,[]) )) to avoid detecting each dot as similar to itself. Finally, it requires that all coordinates (all(...,1)) be the same in order to declare two dots as crashing, and applies find to locate those dots. The result (ii) is a linear index into a 3D array of dimensions path length × number of dots × number of dots, which is translated by ind2sub into position along path and identities of crashing dots.

Answer 2

A=[1 2 ;3 4];B=[5 6;3 9];
A==B
ans =
     0     0
     1     0

This works in 2D, but also in 3D. You can find the location of the equal numbers by using find:

C=permute(A,[3 2 1]);
D=permute(B,[3 2 1]);
find(C==D)
ans =
     3

where 3 is a linear index to the location of the equal number.

for ii = 1:size(A,3)-1
    for jj = ii+1:size(A,3)
        [r{ii,jj},c{ii,jj},v{ii,jj}] = find(squeeze(A(:,:,ii))==squeeze(A(:,:,jj)));
    end
end

This will loop over your matrices in the third dimension, i.e. your physical dots. It will squeeze out the 2D matrix per dot and check that against every other dot's 2D matrix. If it finds any, it will store the row, column and value at the intersection in the cells r, c and v, where the indices correspond to the dot numbers, i.e. r{2,4} will give the row numbers of intersections between dot 2 and 4.