pdist2 with wrapping

I have a square area of gridpoints and I'm trying to create a graph where each point is joined to its neighbouring points based on a Chebychev distance. From an earlier question here, I have the following methodology:

M = 50; N = 50;
[I,J] = ndgrid(1:M,1:N);
IJ = [I(:),J(:)];
[W,K] = pdist2(IJ,IJ,'chebychev','Smallest',9);

From here, columns of W containing only 1 can be selected and can be matched with columns of K to get the adjacency matrix. In this case however, I want to create a graph where the edges of the square are wrapped, that is, the leftmost (or topmost) points are also connected to the rightmost (or bottommost) points. How can I add this condition in pdist2?

Answer 1

[Rik]

You could maybe modify the internal code of pdist2, but you should not do that. The easiest way here is to just create copies of your array with repmat. Don't forget to remove the padding from the result as well.

[Tejas]

Sorry, but I don't understand. You mean manually create connections of the edge points and add them to the adjacency matrix?

[Rik]

I meant something like this:

IJ=repmat(IJ,3,3);
[W,K] = pdist2(IJ,IJ,'chebychev','Smallest',9);

You will have to do something with W and K to account for all the rows and columns you added.

[Tejas]

Wouldn't that be very inefficient? I think the manual method takes far lesser time. I already have a method to create a rectangular graph where the gridpoints are connected vertically, horizontally, and diagonally. I only want to ensure the edges are connected as well, so that every point in the graph will have 8 nearest neighbours at a (Chebychev) distance of 1.

[Rik]

I never claimed this would be efficient. It would work, that is all.

Answer 2

[Tejas]

I have the following manual (and rugged) method for this question, while someone formulates an elegant and efficient solution. The graph (G) is created using a method given here. This graph is an MxN rectangular grid where the gridpoints are connected vertically, horizontally and diagonally to their neighbouring gridpoints. I use the Chebychev distance, so that the diagonal distances are also 1 instead of sqrt(2). The following code connects the points on the leftmost (or topmost) edges to rightmost (or bottommost) edge. This implies every node has eight nearest nodes at a distance of 1.

% Given graph G, dimensions M horizontally and N vertically
xe = M; ye = N;
s = repelem(sub2ind(p.grid,[xe*ones(1,ye),1:xe],...
    [1:ye,ye*ones(1,xe)]),3);

t = zeros(1,3*ye); j = 4;
t(1) = ye; t(2) = 1; t(3) = 2;
t(end-2) = ye-1; t(end-1) = ye; t(end) = 1;
for i = 1:ye-2
    t(j) = i; t(j+1) = i+1; t(j+2) = i+2;
    j = j + 3;
end
t1 = sub2ind([M,N],ones(1,length(t)),t);

t = zeros(1,3*xe); j = 4;
t(1) = xe; t(2) = 1; t(3) = 2;
t(end-2) = xe-1; t(end-1) = xe; t(end) = 1;
for i = 1:xe-2
    t(j) = i; t(j+1) = i+1; t(j+2) = i+2;
    j = j + 3;
end
t2 = sub2ind([M,N],t,ones(1,length(t)));

t = [t1,t2];
idx = find(ismember([s',t'],[t',s'],'rows'),1); s(idx)=[]; t(idx)=[];
st = unique([s;t],'rows');

G = addedge(G,st(1,:),st(2,:),ones(1,length(st)));