Matlab: How to output a matrix which is sorted by distance

Question

I have a cluster of points in 3D point clouds, says

    A = [ 1 4 3;
    1 2 3;
    1 6 3;
    1 5 3];

The distance matrix then was found:

    D= pdist(A);
    Z= squareform(D);
    Z =

 0     2     2     1
 2     0     4     3
 2     4     0     1
 1     3     1     0

I would like to sort the points so that the sum of the distance travelled through the points will be the smallest, and output in another matrix. This is similar to TSP problem but in a 3D model. Is there any function can do this? Your help is really appreciated in advance.

Answer 1

This could be one approach and must be efficient enough for a wide range of datasizes -

D = pdist(A);
Z = squareform(D);  %// Get distance matrix

N = size(A,1);      %// Store the size of the input array for later usage
Z(1:N+1:end) = Inf; %// Set diagonals as Infinites as we intend to find
                    %// minimum along each row

%// Starting point and initialize an array to store the indices according
%// to the sorted requirements set in the question
idx = 1;
out_idx = zeros(N,1);
out_idx(1) = idx;

%// Perform an iterative search to look for nearest one starting from point-1
for k = 2:N
    start_ind = idx;
    [~,idx] = min(Z(start_ind,:));
    Z(:,start_ind) = Inf;
    out_idx(k) = idx;
end

%// Now that you have the list of indices based on the next closest one, 
%// sort the input array based on those indices and have the desired output 
out = A(out_idx,:)

Sample run for given input -

A =
     1     4     3
     1     2     3
     1     6     3
     1     5     3
     1     2     3
out =
     1     4     3
     1     5     3
     1     6     3
     1     2     3
     1     2     3

Answer 2

The only way I can see you do this is by brute force. Also bear in mind that because this is brute force, this will scale very badly as the total number of points increases. This is fine for just 4 points, but if you want to scale this up, the total number of permutations for N points would be N! so be mindful of this before using this approach. If the number of points increases, then you may get to a point where you run out of memory. For example, for 10 points, 10! = 3628800, so this probably won't bode well with memory if you try and go beyond 10 points.

What I can suggest is to generate all possible permutations of visiting the 4 points, then for each pair of points (pt. 1 -> pt. 2, pt. 2 -> pt. 3, pt. 3 -> pt. 4), determine and accumulate the distances, then find the minimum distance accumulated. Whichever distance is the minimum will give you the sequence of nodes you need to visit.

Start with perms to generate all possible ways to visit four points exactly once, then for each pair of points, figure out the distances between the pairs and accumulate the distances. Keep considering pairs of points along each unique permutation until we reach the end. Once we're done, find the smallest distance that was generated, and return the sequence of points to generate this sequence.

Something like:

%// Your code
A = [ 1 4 3;
    1 2 3;
    1 6 3;
    1 5 3];
D = pdist(A);
Z = squareform(D);

%// Generate all possible permutations to visit for our points
V = perms(1:size(A,1));

%// Used to accumulate our distances per point pair
dists = zeros(size(V,1), 1);

%// For each point pair
for idx = 1 : size(V,2)-1
    %// Get the point pair in the sequence
    p1 = V(:,idx);
    p2 = V(:,idx+1);

    %// Figure out the distance between the two points and add them up
    dists = dists + Z(sub2ind(size(Z), p1, p2));
end

%// Find which sequence gave the minimum distance travelled
[~,min_idx] = min(dists);

%// Find the sequence of points to generate the minimum
seq = V(min_idx,:);

%// Give the actual points themselves
out = A(seq,:);

seq and out give the actual sequence of points we need to visit, followed by the actual points themselves. Note that we find one such possible combination. There may be a chance that there is more than one possible way to get the minimum distance travelled. This code just returns one possible combination. As such, what I get with the above is:

>> seq

seq =

     3     4     1     2

>> out

out =

     1     6     3
     1     5     3
     1     4     3
     1     2     3

What the above is saying is that we need to start at point 3, then move to point 4, point 1, then end at point 2. Also, the sequence of pairs of points we need to visit is points 3 and 4, then points 4 and 1 and finally points 1 and 2. The distances are:

• Pt. 3 - Pt. 4 - 1
• Pt. 4 - Pt. 1 - 1
• Pt. 1 - Pt. 2 - 2
• Total distance = 4

If you take a look at this particular problem, the minimum possible distance would be 4 but there is certainly more than one way to get the distance 4. This code just gives you one such possible traversal.