anticlockwise points coordinates sorting

Hi,

I have the follwoing points cooridnates:

A = [0 0 ;
    1 0.2;
    0 1  ;
    0 0.6;
    1 0  ;
    1 1  ;
    0.6 1;
    0.2 0;
    0 0  ;
    0.2 1;
    0 0.2;
    0.6 0;
    1 0.6];

I would like to sort these points in a way that they resmbles points on a square polygon in an anticloskwise direction, as follwoing:

B = [0 0 ;
    0.2 0;
    0.6 0;
    1 0  ;
    1 0.2;
    1 0.6;
    1 1  ;
    0.6 1;
    0.2 1;
    0 1  ;
    0 0.6;
    0 0.2;
    0 0];

%here is how to visulaise the points
figure;
plot(A(:,1),A(:,2),'rx','LineWidth',2)

Any idea how to sort/arrange these points?

Thanks.

Answer 1

[Les Beckham]

A = [0      0 ;
     1      0.2;
     0      1  ;
     0      0.6;
     1      0  ;
     1      1  ;
     0.6    1;
     0.2    0;
     0      0  ;
     0.2    1;
     0      0.2;
     0.6    0;
     1      0.6];
c = [mean(A(:,1)), mean(A(:,2))]; % centroid of the points
d = A - c; % vectors from points to centroid
angles = atan2d(d(:,1), d(:,2)); % angles from centroid to each point
[~,idx] = sort(angles, 'descend'); % sort the angles anti-clockwise
B = A(idx, :) % sort the points based on the angles

B = 13×2

0.6000 0 1.0000 0 1.0000 0.2000 1.0000 0.6000 1.0000 1.0000 0.6000 1.0000 0.2000 1.0000 0 1.0000 0 0.6000 0 0.2000

plot(B(:,1),B(:,2), 'rx')
grid on
hold on
text(B(:,1), B(:,2), sprintfc('%d', 1:numel(idx)))
plot(c(1), c(2), 'bo')

[LH]

Thanks. Clearly the method you presented works, but the points that spread on the bottom edge, i.e., and are not on the top of the 2D matrix. half of them are at the bottom. I understand that one way to correct this is to shift these points, but is there a generic solution that lay the points coordinates correctly together based on their edges (the points on the first (bottom) edge are on the top of the matrix, then the points on the second (right) edge, and so on so forth)?

[Les Beckham]

Try this

A = [0      0;
     1      0.2;
     0      1;
     0      0.6;
     1      0;
     1      1;
     0.6    1;
     0.2    0;
     0      0;
     0.2    1;
     0      0.2;
     0.6    0;
     1      0.6];
c = [mean(A(:,1)), mean(A(:,2))]; % centroid of the points
d = A - c; % vectors from points to centroid
angles = atan2d(d(:,2), d(:,1)); % angles from centroid to each point
angles(angles<-135) = angles(angles<-135) + 360; % offset so the [0, 0.2] point will be last
[~,idx] = sort(angles); % sort the angles
B = A(idx, :) % sort the points based on the angles

B = 13×2

0 0 0 0 0.2000 0 0.6000 0 1.0000 0 1.0000 0.2000 1.0000 0.6000 1.0000 1.0000 0.6000 1.0000 0.2000 1.0000

plot(B(:,1),B(:,2), 'rx')
grid on
hold on
text(B(:,1), B(:,2), sprintfc('%d', 1:numel(idx)))
plot(c(1), c(2), 'bo')

[LH]

Thank you for this.

What if another set of points are presented in matrix A, then another point will be an offset and need to be adjusted so that the sorted matrix starts with [0 0] and ends with [0 0]. The tricky thing is when A is very large, how this can be automated to include all options of A so that its sorted matrix is properly anticlockwised?

In other words, how to say: "start calculating the angles from the fourth quadrant, i.e., from the point (0,0) so that the sorting afterwards starts from this point onwards in an anticlockwise direction?"

Also in another words, how to say: "shift my coordinates matrix so it starts with point (0 0) and ends with point (0 0) for any concave polygon?"

[Les Beckham]

You're welcome.

Have you tried applying this approach to other "polygons"? I suspect that it will work for anything that is similar to this example.

If this answer solved your original problem I would appreciate it if you click the "Accept this answer" button.

[LH]

I will give it a try. Thanks again.

[Les Beckham]

You are quite welcome.