Sorting Points (2D) clockwise

Hello is there a function or easy way to sort 2D Points clockwise?

For example:

Given:

x = (-1,-1)

y = (4,2)

z = (-1,4)

Answer: Sorted clockwise: (y,x,z)

Thank you

Answer 1

[Adam Danz]

Clockwise about what center point?

And what decides the starting coordinate?

If you want to sort 2D coordinates by their polar angle relative to (0,0) in the clockwise direction, convert the Cartesian coordinates to polar coordinates, wrap the radian angle values to [0:2*pi], then sort the results in descending order for the clockwise direction. The first value will be the coordinate closest to 2*pi radians.

data = [-1 -1; 4 2; -1 4]

data = 3×2

-1 -1 4 2 -1 4

figure()
plot(data(:,1), data(:,2), 'o')
text(data(:,1)+0.2,data(:,2),{'x','y','z'})
axis equal
axis padded
grid on

% Convert to polar coordinates
rad = cart2pol(data(:,1), data(:,2));
radWrapped = mod(rad,2*pi);
radWrapped(radWrapped==0 & rad>0) = 2*pi; 
[~, sortIdx] = sort(radWrapped, 'descend'); 

text(data(:,1)-0.2, data(:,2),compose('%d',sortIdx),'HorizontalAlignment', 'right')

[Adam Danz]

Daniela Würmseer's comment moved here from the answers section

-------------------------------------------------------------------------------------

Thank you.

If i try out your Code (@Adam Danz) with data = [0 -1; -1 0; -1 -1] then sortIdx = 1 3 2

but if i try out the code with the two first points exchanged so data = [-1 0; 0 -1; -1 -1]; then sortIdx = 2 3 1. This makes no sense to me normally sortIdx should be 3 1 2 or ?

[Adam Danz]

The sortIdx is the order of the input values. Your input values change order so the sortIdx is expected to change order, too.

This demo below shows that the sorted inputs are the same for both sets of values.

data = [0 -1; -1 0; -1 -1];
% Convert to polar coordinates
rad = cart2pol(data(:,1), data(:,2));
radWrapped = mod(rad,2*pi);
radWrapped(radWrapped==0 & rad>0) = 2*pi;
[~, sortIdx] = sort(radWrapped, 'descend');
sortedData = data(sortIdx,:)

sortedData = 3×2

0 -1 -1 -1 -1 0

data2 = [-1 0; 0 -1; -1 -1];
% Convert to polar coordinates
rad = cart2pol(data2(:,1), data2(:,2));
radWrapped = mod(rad,2*pi);
radWrapped(radWrapped==0 & rad>0) = 2*pi;
[~, sortIdx2] = sort(radWrapped, 'descend');
sortedData2 = data(sortIdx,:)

sortedData2 = 3×2

0 -1 -1 -1 -1 0

The variables sortIdx and sortIdx2 show the indices of the input rows.

[Daniela Würmseer]

Thank you

[Adam Danz]

Happy to help.

[Daniela Würmseer]

@Adam Danz

I have the three (generated) Points:

(0,0)

(-20,4.4963)

(-19.8955, 3.9739)

if i sort those vectors with the function above they stay in this order.

But normally sorted they should be like:

(0,0)

(-19.8955, 3.9739)

(-20,4.4963)

The same i get with some other Points. Do you know why the Polarcoordinate of (-20,4.4963) is smaller than (-19.8955, 3.9739)?

[Adam Danz]

@Daniela Würmseer one of your data points lies on (0,0). This solution sorts in clockwise, descending order starting at angle 0 which is, by convention, at 3 o'clock (from (0,0) to (0,x) where x is >0). Any data point at 0 degrees will be sorted last since the sort is in descending order. If you'd like points at 0 deg to be considered at 2pi, you can change this part of my answer

radWrapped(radWrapped==0 & rad>0) = 2*pi; 

to

radWrapped(radWrapped==0 & rad==0) = 2*pi; 

Another solution would be to center your data using

dataCentered = data - mean(data,1);  % Assuming data is nx2

and then perform the solution in my answer on the centered data.

[Daniela Würmseer]

@Adam Danz Thank you. But for some points i still get an Error in my Algorithm for example:

The following 3 Points are already sorted but

-0.0020   -5.0000        
-0.0010   -5.0041         
-0.0017   -8.5690

Sorted it should look like

-0.0020   -5.0000   
-0.0017   -8.5690
-0.0010   -5.0041         

Do you know what is wrong here?

[Adam Danz]

Are these [x,y] coordinates? If so, the values in row-2 of the sorted list (-0.0017, -8.569) doesn't exist in the initial list. It looks like you're sorting x and y independently but, if I understand your comments correctly, you should be sorting the (x,y) pairs.

[Daniela Würmseer]

d = [-0.0020 -5.0000;

-0.0017 -8.5690;

-0.0010 -5.0041];

sort(d)

So i have a Matrix like d and each row of d is supposed to be a point (coordinates). And i want to sort all the points.

Is the declaration from d for this wrong?

[Adam Danz]

You must be doing something different from my answer. In your example, you'd want sortrows.