Puzzler: Quickly tell if two absolute indices (a,b) are four connected for n x m matrix.
Doug Hull asked
on 1 Sep 2011
Latest activity:
Comment by Walter Roberson
on 2 Sep 2011
function flag = isFourConnected(a,b,n,m) % % a,b: indices of interest a ~= b % n,m: size of matrix of interest % % flag: True if indices a and b are four connected % in a matrix of size n x m % % % Your code here Note, this code should use no toolboxes, and should be reasonably quick as this function will be called many times. Reasonably quick is up to debate as the rest of the code forms. Products |
|---|
6 answers
David Young answered
on 1 Sep 2011
Accepted answer
function flag = isFourConnected(a,b,n,m) % % a,b: indices of interest a ~= b % n,m: size of matrix of interest % % flag: True if indices a and b are four connected % in a matrix of size n x m %
d = abs(a-b); flag = d == n || (d == 1 && mod(min(a,b), n));
end
3 comments
Walter Roberson
on 1 Sep 2011
Interesting way to code the top vs bottom boundary condition.
andrei bobrov
on 2 Sep 2011
Hi David! +1
David Young
on 3 Sep 2011
Thanks Doug!
Walter Roberson answered
on 1 Sep 2011
function flag = isFourConnected(a,b,n,m) % % a,b: indices of interest a ~= b % n,m: size of matrix of interest % % flag: True if indices a and b are four connected % in a matrix of size n x m % % flag = abs(a-b)==n || (floor(a/n)==floor(b/n) && abs(a-b)==1);
3 comments
Walter Roberson
on 1 Sep 2011
Saving a repeated calculation to a variable isn't always faster once you take the JIT into account.
That's my excuse, and I'm sticking to it :-)
Walter Roberson
on 1 Sep 2011
flag = abs(a-b)==n || (abs(a-b)==1 && floor(a/n)==floor(b/n));
David Young
on 1 Sep 2011
Neat
Fangjun Jiang answered
on 1 Sep 2011
Circle-shifting neighbors are considered connected.
function flag = isFourConnected(a,b,n,m) % % a,b: indices of interest a ~= b % n,m: size of matrix of interest % % flag: True if indices a and b are four connected % in a matrix of size n x m % % % Your code here [x,y]=ind2sub([n,m],[a;b]); xdiff=abs(x(1)-x(2)); ydiff=abs(y(1)-y(2));
flag = ((xdiff==0) && (ydiff==1) || (ydiff==m-1)) || ...
((ydiff==0) && (xdiff==1) || (xdiff==n-1));
A little test script. All other entries so far didn't pass this test.
clc;
TestVector={6,7,4,5
6,10,4,5
1,4,4,5
1,17,4,5};
for k=1:size(TestVector,1)
if isFourConnected(TestVector{k,:})~=true
disp(k);beep;
end
end
1 comment
Doug Hull
on 1 Sep 2011
clever, I like it! First in also! Thanks (will accept after a few hours to let more people at it!)
Oleg Komarov answered
on 1 Sep 2011
I assume a,b,m,n always numeric and integer values > 1
function flag = isFourConnected(a,b,n,m)
% a,b : indices of interest a ~= b % m,n : size of matrix of interest % flag: True if indices a and b are four connected % in a matrix of size n x m
d = a-b; flag = d == n || d == -n || (d == 1 && mod(a,n) ~= 1) || (d == -1 && mod(b,n) ~= 1);
4 comments
Show
1 older comment
Walter Roberson
on 1 Sep 2011
df would be 1 for bottom of column vs top of next column
Oleg Komarov
on 1 Sep 2011
Argh...
Oleg Komarov
on 1 Sep 2011
Can't find any other valid solution to ensure bottom vs top not 4 conn except the ones already proposed.
Walter Roberson
on 1 Sep 2011
Tossing something together: diff(mod(sort([a,b]),n))<0
Bruno Luong answered
on 1 Sep 2011
function flag = isFourConnected(a,b,n,m) % 10 arithmetic operations by pair
c = max(a,b); d = min(a,b); e = c - d; flag = (e==1 & mod(d,n)) | (e==n & c>n);
2 comments
Walter Roberson
on 1 Sep 2011
This might or might not be slightly faster:
c = sort([a,b]);
e = c(2)-c(1);
flag = (e==1 & mod(c(1),n)) | (e==m & c(2)>n);
Or if you prefer your original structure, then instead of max/min, you could use
c = max(a,b);
d = a + b - c;
Bruno Luong
on 1 Sep 2011
I believe I had one redundant test in the earlier code:
function flag = isFourConnected(a,b,n,m)
% 8 arithmetic operations by pair
c = max(a,b);
d = min(a,b);
e = c - d;
flag = (e==1 & mod(d,n)) | (e==n);
Daniel answered
on 2 Sep 2011
I am not sure what to do about circle-shifting neighbors so I have two answers.
function flag = isFourConnected(a,b,n,m) % % a,b: indices of interest a ~= b % n,m: size of matrix of interest % % flag: True if indices a and b are four connected % in a matrix of size n x m % % % Your code here
% Using ind2sub might be faster. col = mod([a(:), b(:)]-1, n)+1; row = ceil([a(:), b(:)]/n); %[col, row] = ind2sub([n, m], [a(:), b(:)]);
flag = reshape(mod(abs(diff(col, 1, 2)), n-2)+mod(abs(diff(row, 1, 2)), m-2) == 1, size(a));
% if circle shifted points are not connected: % flag = reshape(abs(diff(col, 1, 2))+abs(diff(row, 1, 2)) == 1, size(a));
0 comments
Contact us at files@mathworks.com
10 comments
I need clarification regarding "absolute indices" and "four connected". Can you give a numerical example?
I think I figured it out now. Every element in a matrix has four connected, left, right, top, bottom. Absolute indices means linear indices or single indices.
@Fangjun
Correct!
is a point considered to be 4 connected to itself?
@Walter:
good edge case. Editing question to deal with this.
Which, if any, of the input arguments does the function need to be vectorizable across?
How about circle-shifting neighbors? Should isFourConnected(1,4,4,5) and isFourConnected(1,17,4,5) all be true?
for three-dimensional array
d = abs(a-b);
flag = d == n || d == n*m || (d == 1 && mod(min(a,b), n));
@andrei, your code above returns false for both (1,4,4,5) and (1,17,4,5)
Did anyone run timing tests on the survivors?