How can I sort an array to follow a path?

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.

[Adam Danz]

When I see 'circumference' I'm expecting circles. I don't see anything circular in your figure.

I also don't know what this means: "the data points are not following the path". What path?

I'm not sure how sorting comes into play.

[george a]

Oh sorry, what I meant was perimeter. I obtain this data points on the perimeter but their order is a bit random I want to change the order to follow the path of the perimeter. I uploaded the figure with first 6 data point.

[Adam Danz]

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]

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.

Answer 1

[Adam Danz]

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

[george a]

Thank you, I also tried convex hull and alpha shape approach but came back to proximity based sorting,

[Adam Danz]

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.

[george a]

Thank you very much