Organize Points and Draw the Line

Question

In Matlab, I've got several points in the 3D space. Those points represent a rope and I would like to draw a line linking all those points. Here is my problem: How the oraganization of those points should be done to have a "simple" and "more or less straigth line". In other words I would like to draw a line linking all the points from the first to the last one but not "going back". Maybe with a simple image i can explain better my problem:

This is what the code should do:

This is what the code shouldn't do:

Some idea of how can I achieve the intended result? How can I organize the points? I'm working with Matlab but if you know any paper where I can read how to do this it will be fine. Thank you.

Answer 1

If you just don't want to go back in the upper direction, the solution that @Dan suggested should be fine. Sort them in that direction before connecting.

However, if that is not a requirement but you are actually looking for a solution without ugly crossings that is as short as possible, you may want to look into solutions for the travelling salesman problem.

If you define the distance between 1 and 9 to be zero, the solution you find to the travelling salesman problem should give you a nice and short rope.

---

If you want to go for the TSP approach but get a little lost, just try a 'furthest insertion' start position or '2 opt' improvements as that is likely going to give a big improvement over random path selection already with minimal effort.

Answer 2

OK. I've found the right answer (by Gunther Struyf): Sort Coordinates Points in Matlab

In order to visualize the final result just add to Gunther's code the following lines:

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

The following code shows the same algorithm but for a 3D implementation:

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));