代码之家 › 专栏 › 技术社区 › Elayne Eng Teng Sin

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

point-clouds matrix matlab

Elayne Eng Teng Sin · 技术社区 · 10 年前

“我在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模型中。有什么功能可以做到这一点吗? 我们非常感谢您的帮助。

2 回复 | 直到 10 年前

Divakar 10 年前

这可能是一种方法,并且必须对广泛的数据大小足够有效-

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

rayryeng 10 年前

我唯一能看到你这样做的方法就是用暴力。还要记住,因为这是蛮力,所以随着积分总数的增加,这会扩展得很厉害。这仅适用于4个点,但如果您想将其放大 N 点数将是 N! 因此,在使用此方法之前,请注意这一点。如果点数增加,则可能会出现内存不足的情况。例如对于10个点, 10! = 3628800 ,所以如果你试图超过10分,这可能对记忆力来说不是个好兆头。

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

从开始 perms 为了生成所有可能的方法来精确访问四个点一次,然后针对每对点,计算出这对点之间的距离并累加距离。继续考虑沿着每个唯一排列的成对点,直到我们到达终点。完成后,找到生成的最小距离,并返回点序列以生成此序列。

类似于:

%// 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 给出我们需要访问的点的实际顺序,然后是实际点本身。注意,我们发现了一种这样的可能组合。可能有不止一种可能的方法来获得最小行驶距离。此代码只返回一个可能的组合。因此,我从上面得到的是:

>> 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。这段代码只为您提供了一种可能的遍历。