Sort coordinates based on closest connectivity?

Hello,

I have an nx3 array representing x,y,z coordinates in space. These coordinates are all connected and represent a tortuous line. I would like to calculate the length of this line, however the coordinates I have are not in order of connectivity. Is it possible to reorder them such that I can simply calculate the length by doing a for loop like:

length = 0;
for i = 1:length(array)-1
    length = norm([coords(i,1)-coords(i+1,1),coords(i,2)-coords(i+1,2),coords(i,3)-coords(i+1,3)]);
end

I have tried just finding the neighbours of each coordinate and reordering that way, but this gets very convoluted quickly and requires that I "walk" through the line. For the total dataset I am trying to analyze I will literally have millions of these lines, so I am trying to avoid slow solutions like that.

Edit: The lines I'm working with are in an image, and the points on the line must have a max distance from each consecutive point of (1,1,1). That is, 1 pixel in x,y, and z.

Answer 1

[Image Analyst]

Try https://www.mathworks.com/matlabcentral/answers/?term=tag%3A%22traveling+salesman+problem%22

[Eric Chadwick]

Hello,

Thank you! This looks like what I need. However it is very slow since it is required to iterate. Do you have any other suggestions that might be quicker? Again I need to do this for literally millions of lines so I need to limit processing time where I can.

Thanks,

Eric

[Image Analyst]

Well if you just want to go to the next closest unvisited point, you could use sqrt to find out which is closest. This greedy search wouldn't necessarily give the shortest overall path (as solving the traveling salesman problem would), but it will give a path. Here, try this and see if it's what you want:

clc;    % Clear the command window.
close all;  % Close all figures (except those of imtool.)
clear;  % Erase all existing variables. Or clearvars if you want.
workspace;  % Make sure the workspace panel is showing.
format long g;
format compact;
fontSize = 20;

% Initial setup
numPoints = 10;
x = rand(1, numPoints);
y = rand(1, numPoints);
plot(x, y, 'bo', 'LineWidth', 2, 'MarkerSize', 17);
grid on;
% Make axis square so we don't get deceived on distances in x and y directions.
axis square;
xlabel('X', 'FontSize', fontSize);
ylabel('Y', 'FontSize', fontSize);
% Enlarge figure to full screen.
set(gcf, 'Units', 'Normalized', 'OuterPosition', [0, 0.08, 1, 0.92]);
% Label ths points
for k = 1 : numPoints
  text(x(k), y(k), num2str(k), 'FontSize', 15, 'Color', 'b');
end

% Make a list of which points have been visited
beenVisited = false(1, numPoints);
% Make an array to store the order in which we visit the points.
visitationOrder = ones(1, numPoints);
% Define a filasafe
maxIterations = numPoints + 1;
iterationCount = 1;
% Visit each point, finding which unvisited point is closest.
% Define a current index.  currentIndex will be 1 to start and then will vary.
currentIndex = 1;
while sum(beenVisited) < numPoints && iterationCount < maxIterations
  % Indicate current point has been visited.
  visitationOrder(iterationCount) = currentIndex; 
  beenVisited(currentIndex) = true; 
  % Get the x and y of the current point.
  thisX = x(currentIndex);
  thisY = y(currentIndex);
  text(thisX + 0.01, thisY, num2str(currentIndex), 'FontSize', 35, 'Color', 'r');
  % Compute distances to all other points
  distances = sqrt((thisX - x) .^ 2 + (thisY - y) .^ 2);
  % Don't consider visited points by setting their distance to infinity.
  distances(beenVisited) = inf;
  % Also don't want to consider the distance of a point to itself, which is 0 and would alsoways be the minimum distances of course.
  distances(currentIndex) = inf;
  % Find the closest point.  this will be our next point.
  [minDistance, indexOfClosest] = min(distances);
  % Save this index
  iterationCount = iterationCount + 1;
  % Set the current index equal to the index of the closest point.
  currentIndex = indexOfClosest;
end
visitationOrder
% Plot lines in that order.
hold on;
plot(x(visitationOrder), y(visitationOrder), 'm-', 'LineWidth', 2);
title('Start with 1 and visit next closest in order', 'FontSize', fontSize);

[Eric Chadwick]

Hi Image Analyst.

I actually figured out another way to do it that steps through each point, but I was already doing that for another purpose so I just added a few lines to create a connectivity matrix based on the neighbours of each point. From here I used this function:

https://www.mathworks.com/matlabcentral/fileexchange/51610-hamiltonian-graph--source--destination-?focused=3883152&tab=function

which gave me the order I desired. I will mark yours as the accepted answer since it seems like your code does something very similar.

I do have one question. I can probably brute force it, but is there already a function that takes in an array and a "order" vector and rearranges the array in the order specified by the vector?

For example:

Array = [5 4 2 1 3]; Order = [4 3 5 2 1];

Output = somefunction(Array,Order) = [1 2 3 4 5];

Edit: Found the function. It is called 'permute' for anyone else who finds this thread.

Cheers,

Eric

[Image Analyst]

Yes.

outputArray = inputArray(Order);

permute() does something different than you described. It moves around dimensions rather than reorders. Like swapping rows and columns, essentially transposing for just one example.

[Asyran Abdullah]

As shown in figure, how to make the point connect more than 1 connection to other nodes? Example: 1-2-3-4-1-3-6-7

[Image Analyst]

I don't see any rationale for how you're connecting the points in the figure

in that order, [1-2-3-4-1-3-6-7]. How is that order decided? If it's just arbitrary, then you can still do

outputArray = inputArray(Order);

with whatever order you want.

[Walter Roberson]

Asyran Abdullah comments to Image Analyst

Thanks it's good