1

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. enter image description here

Ali_d
  • 1,089
  • 9
  • 24
  • 1
    I suggest starting from reading https://stackoverflow.com/questions/6989100/sort-points-in-clockwise-order – Daweo May 28 '21 at 08:45
  • Dear @Daweo, I read this solution. thanks for sending it to me. But unfortunately it is not in Pythun and I think for me it makes more sens if I find a way to sort point based on `x` and `y` values. – Ali_d May 28 '21 at 08:50
  • Does this answer your question? [Sort points in clockwise order?](https://stackoverflow.com/questions/6989100/sort-points-in-clockwise-order) –  May 28 '21 at 08:51
  • Dear @Paul, unfortunately it does not help me because it is not in python and believe for me it will be more efficient if I work on `x` and `y` value. I want a way to make the pattern of my points as an algorthm. – Ali_d May 28 '21 at 08:53
  • 2
    Dear @Ali_d, I strongly suggest you read the question and answers that were linked in the comments. This link contains exactly the answers that you are asking for. Indeed they are not in python. The answers describe algorithms. Implementing these algorithms in python is your job. – Stef May 28 '21 at 09:13

3 Answers3

3
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

Thomas Kimber
  • 10,601
  • 3
  • 25
  • 42
  • Dear @Thomas Kimber, I tried your method but unfortunately it fails for other arrangements of points. Can you please have a look at this example for me: `points=[[1.,3.],[1.,4.],[2.,2.],[2.,4.],[3.,1.],[3.,4.],[4.,1.],[4.,2.],[4.,3.],[4.,4.]]`. The new ordered points do not follow the pattern I want. Sorry for making that much trouble. – Ali_d May 28 '21 at 09:23
  • 1
    Here's the order I get `[[1.0, 4.0], [1.0, 3.0], [2.0, 4.0], [3.0, 4.0], [2.0, 2.0], [4.0, 4.0], [4.0, 3.0], [4.0, 2.0], [3.0, 1.0], [4.0, 1.0]]`. Which when I plot on paper looks ok - again (2,2) and (4,4) share the same angle, so it's undetermined which you might want to appear first in a clockwise sweep from the origin. But making the suggested polar_coordinates change sorts that out. What order do you want for that collection of points? – Thomas Kimber May 28 '21 at 09:30
  • I know your algorithm is fine but I want to have it as `[[1.0, 3.0], [1.0, 4.0], [2.0, 4.0], [3.0, 4.0], [4.0, 4.0], [4.0, 3.0], [4.0, 2.0], [4.0, 1.0], [3.0, 1.0], [2.0, 2.0]]`. I really do not know how to say it geometrically. If you plot them and look at my sort in this comment, you will get my logic. Thanks again. – Ali_d May 28 '21 at 09:35
  • I want to create a polygon by these points and each point should be connected to the next one. So, I want to order them in this way. – Ali_d May 28 '21 at 09:36
  • 1
    OK, so you want them to be listed clockwise *from the centre of the figure* rather than from the *origin of the coordinate system*. Just set the `centre_of_rotation_xy_coord` to a coordinate located within your shape - say, at position (3,3) and you'll get the order you want. If I do this, I get `[[2.0, 2.0], [1.0, 3.0], [1.0, 4.0], [2.0, 4.0], [3.0, 4.0], [4.0, 4.0], [4.0, 3.0], [4.0, 2.0], [4.0, 1.0], [3.0, 1.0]]` – Thomas Kimber May 28 '21 at 09:37
2

One way would be to compute the angle of each point with respect the center (mean of all points for example), and then sort the points according to the angle. To compute the angle, you can use the atan2 function.

If the results from that method don't give the order you desire, search for the TSP (Travelling Salesman Problem). In general is difficult to solve (is a NP problem) but it can be solved exactly if the numbers of points is small. If the number of points is large, then there are algorithms that approximately find a good solution.

Diego Palacios
  • 1,096
  • 6
  • 22
  • Thanks for devoting time to my issue. Don't you think it is possible to make the pattern of points as an algorithm? I am afraid maybe angle does not work. – Ali_d May 28 '21 at 08:56
  • 1
    I'm not sure what do you mean by 'pattern of points'. What you are trying to solve is to find the polygon that has these points. However, there are multiple polygons that fit your points (the solution is not unique). Therefore, you must choose a criterion to find your polygon. Solving the TSP will give you the polygon with the shortest perimeter. The angle sorting algorithm will probably give you another (or the same) polygon. If non of these methods give what you want, you must first have clear what is your criterion to find the order of the points. Your current criterion is not well defined. – Diego Palacios May 28 '21 at 09:03
1

To copy the answer from @Thomas Kimber, this is a version in numpy that also calculates the center point by taking the mean of all points in each dimension:

def rotational_sort(list_of_xy_coords):
    cx, cy = list_of_xy_coords.mean(0)
    x, y = list_of_xy_coords.T
    angles = np.arctan2(x-cx, y-cy)
    indices = np.argsort(angles)
    return list_of_xy_coords[indices]
Zoom
  • 400
  • 1
  • 5
  • 20