How to sort coordinates in python in a clockwise direction

Question

I have some coordinate points as list which are sorted firstly based on the x and then y values. I tried this solution and also this one but it did not work for me. This is a simplified set of my points:

points=[[0.,0.],[0.,1.],[1.,0.],[1.,1.],[1.,2.],[1.,3.],[2.,0.]]

I want to resort them in a clockwise angle. My fig clearly shows it. I start from the first point (it is (0,0) here) and put other point which have the same x value but their y is higher. Then, I go for the points that their x values is 1 and sort from higher y values to lower ones. After point (1,1) I have two points with the same y and I pick first the point with higher x. Finally I want to to have my sorted list as:

resor_poi=[[0.,0.],[0.,1.],[1.,3.],[1.,2.],[1.,1.],[2.,0.],[1.,0.]]

I do appreciate any help in advance.

Answer 1

from math import atan2

def argsort(seq):
    #http://stackoverflow.com/questions/3382352/equivalent-of-numpy-argsort-in-basic-python/3382369#3382369
    #by unutbu
    #https://stackoverflow.com/questions/3382352/equivalent-of-numpy-argsort-in-basic-python 
    # from Boris Gorelik
    return sorted(range(len(seq)), key=seq.__getitem__)

def rotational_sort(list_of_xy_coords, centre_of_rotation_xy_coord, clockwise=True):
    cx,cy=centre_of_rotation_xy_coord
    angles = [atan2(x-cx, y-cy) for x,y in list_of_xy_coords]
    indices = argsort(angles)
    if clockwise:
        return [list_of_xy_coords[i] for i in indices]
    else:
        return [list_of_xy_coords[i] for i in indices[::-1]]

points=[[0.,0.],[0.,1.],[1.,0.],[1.,1.],[1.,2.],[1.,3.],[2.,0.]]
rotational_sort(points, (0,0),True)



[[0.0, 0.0],
[0.0, 1.0],
[1.0, 3.0],
[1.0, 2.0],
[1.0, 1.0],
[1.0, 0.0],
[2.0, 0.0]]

Notice the last two points have the same angle from the centre, so it's a toss up to say which one should come first.

If you wanted to force closer points to be first, or last in this situation, you could include a secondary metric (say distance) to be included in the thing to be sorted.

e.g. augment the angles list with something that includes a distance value - maybe something like:

polar_coords = [(atan2(x-cx, y-cy), ((x-cx)**2)+((y-cy)**2)) for x,y in list_of_xy_coords]

Which returns the polar coordinates (angle,distance) of the points, which if you then sorted, should resolve these magnitude-tie-breaks in a consistent fashion.

P.S. Credit where it's due - @Diego Palacios's atan2 is precisely the thing to convert from cartesian pairs to angles, there's probably a more tidy way to do the magnitude part of my second calculation along those lines too. I've also "borrowed" a useful argsort function here from an answer to this helpful discussion: Equivalent of Numpy.argsort() in basic python? courtesy of @Boris Gorelik