matlab - 组织点和画线

Question

在Matlab中，我在 3D 空间中有几个点。这些点代表一根绳子，我想画一条连接所有这些点的线。这是我的问题：应该如何组织这些点以获得“简单”和“或多或少的直线”。换句话说，我想画一条线，将所有点从第一个点连接到最后一个点，而不是“回去”。也许用一个简单的图像我可以更好地解释我的问题：

这是代码应该做的：

这是代码不应该做的事情：

关于如何达到预期结果的一些想法？如何组织积分？我正在使用 Matlab，但如果你知道任何我可以阅读如何做到这一点的论文，那就没问题了。谢谢你。

Answer 1

如果您只是不想回到上面的方向，@Dan 建议的解决方案应该没问题。在连接之前按该方向对它们进行排序。

但是，如果这不是必需的，但您实际上正在寻找一个没有丑陋交叉且尽可能短的解决方案，您可能需要研究旅行商问题的解决方案。

如果您将 1 和 9 之间的距离定义为零，那么您找到的旅行商问题的解决方案应该会给您一个不错的短绳。

---

如果您想采用 TSP 方法但有点迷失，只需尝试“最远插入”起始位置或“2 opt”改进，因为这可能会以最小的努力对随机路径选择带来很大的改进。

Answer 2

好的。我找到了正确的答案（Gunther Struyf）：在 Matlab 中排序坐标点

为了可视化最终结果，只需将以下几行添加到 Gunther 的代码中：

row=data(:,1);
col=data(:,2);
figure
scatter(row,col,'r');
hold on
line(row(result),col(result));

以下代码显示了相同的算法，但用于 3D 实现：

close all;
data = [2,2, 2; 2,3,2 ; 1,2,3 ; 1,3,3 ; 2,1,3 ; 1,1,3 ; 3,2,4 ; 3,3,4 ; 3,1,5; 5,4,6; 7,3,8; 8,9,7; 9,4,7; 6,2,5; 5,8,6; 9,3,8;6,9,2];
row=data(:,1);
col=data(:,2);
frame=data(:,3);

dist = pdist2(data,data);

N = size(data,1);
result = NaN(1,N);
result(1) = 1; % first point is first row in data matrix

for ii=2:N
    dist(:,result(ii-1)) = Inf;
    [~, closest_idx] = min(dist(result(ii-1),:));
    result(ii) = closest_idx;
end

figure
%Ploting the points directly (without sorting)
subplot(2,1,1);
scatter3(row,col,frame,'r');
hold on;
line(row,col,frame);
%Ploting after sorting
subplot(2,1,2);
scatter3(row,col,frame,'r');
hold on
line(row(result),col(result),frame(result));