Sort coordinates based on closest connectivity?

Question

Eric Chadwick 2018-2-20

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/383787-sort-coordinates-based-on-closest-connectivity

评论： Walter Roberson 2018-8-29

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.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Image Analyst 2018-2-20

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/383787-sort-coordinates-based-on-closest-connectivity#answer_306145

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

7 个评论
显示 5更早的评论隐藏 5更早的评论

Image Analyst 2018-2-21

编辑：Image Analyst 2018-2-21

在 MATLAB Online 中打开

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