Matlab：如何输出按距离排序的矩阵

Question

我在 3D 点云中有一组点，说

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

然后找到距离矩阵：

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

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

我想对点进行排序，使经过点的距离之和最小，并输出到另一个矩阵中。这类似于 TSP 问题，但在 3D 模型中。有什么功能可以做到这一点吗？非常感谢您的帮助。

Answer 1

这可能是一种方法，并且必须对各种数据大小都足够有效 -

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,:)

给定输入的样本运行 -

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

我能看到你这样做的唯一方法是通过蛮力。还要记住，因为这是蛮力，所以随着总点数的增加，这将非常糟糕。这对于 4 点来说很好，但是如果你想扩大它，N 点的排列总数将是 N!，所以在使用这种方法之前要注意这一点。如果点数增加，那么您可能会达到运行内存不足的程度。例如，对于 10 分，10! = 3628800，因此如果您尝试超过 10 分，这可能对记忆力不利。

我的建议是生成访问 4 个点的所有可能排列，然后针对每对点（pt. 1 -> pt. 2，pt. 2 -> pt. 3，pt. 3 - > pt. 4), 确定并累积距离，然后找到累积的最小距离。无论哪个距离最小，都会为您提供需要访问的节点序列。

从perms开始，生成访问四个点恰好一次的所有可能方式，然后对于每对点，算出对之间的距离并累加距离。继续考虑沿每个唯一排列的点对，直到我们到达终点。完成后，找到生成的最小距离，以及 return 生成此序列的点序列。

类似于：

%// 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 和 out 给出了我们需要访问的点的实际顺序，然后是实际点本身。请注意，我们找到了这样一种可能的组合。可能有不止一种可能的方法来获得最小行驶距离。此代码只是 return 一种可能的组合。因此，我得到的是：

>> seq

seq =

     3     4     1     2

>> out

out =

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

上面说的是我们需要从点3开始，然后移动到点4，点1，然后在点2结束。另外，我们需要访问的点对顺序是点3和4，然后是点4和1，最后是点1和2。距离是：

铂。 3 - 铂。 4 - 1
铂。 4 - 铂。 1 - 1
铂。 1 - 铂。 2 - 2
总距离 = 4

如果你看一下这个特定的问题，最小可能的距离是 4，但是肯定有不止一种方法可以得到距离 4。这段代码只是给你一个这样的可能的遍历。

Matlab：如何输出按距离排序的矩阵

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

matlab

matrix

point-clouds