pdist2 with wrapping

9 views (last 30 days)
Tejas
Tejas on 21 Jan 2021
Commented: Rik on 22 Jan 2021
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?

Answers (2)

Rik
Rik on 21 Jan 2021
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.
  4 Comments
Tejas
Tejas on 22 Jan 2021
Edited: Tejas on 22 Jan 2021
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
Rik on 22 Jan 2021
I never claimed this would be efficient. It would work, that is all.

Sign in to comment.


Tejas
Tejas on 22 Jan 2021
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)));

Tags

Products


Release

R2020a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!