sort pairwise shortest distance

Question

This is my problem.

clc; clear all; close all;  
N = 10;
R = randn(N,1)+10;R(end) = R(1);
tht = linspace(0,2*pi,N).';
x = R.*cos(tht);
y = R.*sin(tht);
plot(x, y,'o-b');

Randomly sorting the arrays

X = x(randperm(size(x,1)),:);
Y = y(randperm(size(y,1)),:);
hold on, plot(X,Y,'o-r');

As it can be seen the contour that is drawn has overlapping regions. so I wanted to draw a non-overlapping closed contour. One idea that I got was by ordering the elements of the matrix such that the adjacent distances between the elements of the matrix are minimum. So the closest points will be adjacent to one another.

Can anyone specify how I can do it ? I tried to use pdist2 but failed.

Answer 1

If I understand you correctly, you want to reorder some vertices such that all the lines drawn between subsequent points form a closed, non-overlapping contour.

This can be accomplished by re-ordering your vertices in a (counter)clockwise fashion about the centre of mass of all the points. In 2D, this can most easily be accomplished by sorting the output of atan2:

%// Compute centre of mass
r_COM = sum([X, Y]) / numel(X);

%// Sort all vertices by angle
[~, I] = sort(atan2(Y - r_COM(2), X - r_COM(1)));

%// Plot the new contour
hold on, plot(X([I; I(1)]),Y([I; I(1)]), '.-k', 'linewidth', 2);

Results: