How to arrange the huge list of 2d coordinates in a clokwise direction in python?

I want to arrange list of 2d coordinates in a clockwise direction using python. I found similar Q&A here and it is working fine for small scale of data. I had a coordinates list of around 200k points and tried to execute same code but it is unable to execute.

    from functools import reduce
    import operator
    import math

    coords = [(1,1),(3,2),...] # Around 200k points    
    coords = list(dict.fromkeys(coords))
    center = tuple(map(operator.truediv, functools.reduce(lambda x, y: map(operator.add, x, y), coords), [len(coords)] * 2))
    final_list = (sorted(coords, key=lambda coord: (-135 - math.degrees(math.atan2(*tuple(map(operator.sub, coord, center))[::-1]))) % 360))

In the above code it is failing to calculate center and program exiting automatically. Is the any thing to change for holding and calculate for huge list of coordinates?

Solution

One way would be first parametrize the coordinates by angle. Like so:

centroid = sum(points)/len(points)
angles = map(lambda x: -atan2(x[1], x[0]), points)
tuples_to_sort = zip(angles, points)
sorted_points = map(lambda x: x[1], sorted(tuples_to_sort))

This works because: 1. Angles is just an angle coming from the origin. 2. we construct a list of tuples where the first element is the angle and the second the point. We do this to later sort it and sorting on tuples is performed on element by element basis so it will sort on angles. 3. We get the original points we want.

However, you're saying that there is a possible performance problem, so you might try using numpy for computations. Numpy is much quicker as it uses lower level concepts under the hood and is optimized for doing efficient array computations. Below is a simple version of the above written using numpy.

import numpy as np

coords = np.array(coords)
center = coords.mean(axis=0)
centered = coords - center
angles = -np.arctan2(centered[:,1], centered[:,0])
sorted_coords = coords[np.argsort(angles)]
result = coords + center

You can obviously make it more concise and give the variables better suited names, but it should work and should be a little bit faster as well.