How can I sort an array to follow a path?

17 views (last 30 days)
Hello everyone,
I have come across a problem that I can't solve, I am obtaining a circumference of a cut but the problem is the data points are not following the path of the circumference. Is there any way to sort the data to follow the path? I hope the figure is clear enough.
  4 Comments
Adam Danz
Adam Danz on 29 Mar 2020
Edited: Adam Danz on 29 Mar 2020
That's clearer. How did you obtain the perimeter points?
Am I correct in envisioning that you have a set of (x0,y0) coordinates that define the perimeter and a 2nd set of (x1,y1) points that define the position of the numeric markers?
george a
george a on 29 Mar 2020
I am obtaining the periemeter points by reading and slicing an .stl file.i put the numeric markers to show the data points. I have a single set of (x,y) coordinates that are on the perimeter however their order not "sequential". I want every data point to follow each other, 2nd data point should be the "neighbor" of the 1st one and 3rd data point should be the "neighbor" of the 2nd one and so on. I dont know how can I change the order of set to obtain this. I thought some methods but they would all fail, like find the neighbor data point by proximity and sort.

Sign in to comment.

Accepted Answer

Adam Danz
Adam Danz on 29 Mar 2020
Edited: Adam Danz on 1 Apr 2020
I don't know much about reading in stl files but you might want to look into options that would read in the points in different ways to them them in sequential order, if it's possible.
Here are two methods that each produce the same figure shown at the bottom.
Method 1 shows a solution using k = convhull(x,y)
% Create coordinates that form a circle
th = linspace(0,2*pi,60);
x = sin(th);
y = cos(th);
% Scatter the order of the coordinates so they
% are no longer sequential
idx = randsample(numel(x), numel(x));
x = x(idx);
y = y(idx);
% Compute 2D convext hull
idx = convhull(x,y);
% Plot before and after sort
figure()
subplot(1,2,1)
plot(x,y,'r-o')
axis square
grid on
title('Original scattered coordinates')
subplot(1,2,2)
plot(x(idx), y(idx), 'r-o')
axis square
grid on
title('Sorted coordinates')
Method 2 shows a solution using proximity. This method relies on the following assumptions:
  • The perimeter line does not cross over itself.
  • The distance between coordinate A and it's neightboring coordinate B is the minimum distance between coordinate A and any other coordinate in the perimeter execept, perhaps the coordinate that come sequentially before A. In other words, if parts of the parimeter come very close to eachother such that their distance is closer than the interval of coordinates, this will fail.
See inline comments for details.
% Create coordinates that form a circle
th = linspace(0,2*pi,60);
x = sin(th);
y = cos(th);
% Scatter the order of the coordinates so they
% are no longer sequential
idx = randsample(numel(x), numel(x));
x = x(idx);
y = y(idx);
% Set up loop variables. The first coordinate
% will be the first coordinate in the new, sorted order.
yIdx = [1,nan(size(y)-1)];
xyTemp = [x(:), y(:)];
xyTemp(1,:) = NaN;
idx = [1, nan(1, numel(x)-1)];
counter = 0;
% Loop through each coordinate and find its nearest neightbor,
% Then eliminate that coordinate from being chosen again, and
% then start the loop again finding the nearest neighbor to
% the pointe we just located.
while any(isnan(idx))
counter = counter+1;
% find closest coordinate to (x(i),y(i)) that isn't already taken
[~, idx(counter+1)] = min(pdist2(xyTemp,[x(idx(counter)), y(idx(counter))]));
% Eliminate that from the pool
xyTemp(idx(counter+1),:) = NaN;
end
% Plot before and after sort
figure()
subplot(1,2,1)
plot(x,y,'r-o')
axis square
grid on
title('Original scattered coordinates')
subplot(1,2,2)
plot(x(idx), y(idx), 'r-o')
axis square
grid on
title('Sorted coordinates')
  3 Comments
Adam Danz
Adam Danz on 1 Apr 2020
Edited: Adam Danz on 1 Apr 2020
george a, I've updated my answer to show how to use convhull to solve this problem but it may not work on many types of perimeters where the proximity method may work.

Sign in to comment.

More Answers (0)

Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!