an implementation of a robust angle checker

ang_check.py

import numpy as np
import math
import time

# https://docs.python.org/3/howto/sorting.html#sortinghowto
def cmp_to_key(mycmp):
    'Convert a cmp= function into a key= function'
    class K:
        def __init__(self, obj, *args):
            self.obj = obj
        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0
        def __ne__(self, other):
            return mycmp(self.obj, other.obj) != 0
    return K

# sort by computing the angles of each vector and sorting according to them
def angle_cyclic_order(V):

    start = time.time()
    ang = np.zeros(V.shape[1])
    for idx in range(V.shape[1]):
        x,y = V[:,idx]
        ang[idx] = math.atan2(-y,-x)
    sort_order = np.argsort(ang)
    end = time.time()
    return [x for x in sort_order],end-start

# sort by quadrant and then the cross-product area
def cyclic_order(V):
    start = time.time()
    # first compare first the quadrants of two points
    # if they differ then use that result for the comparison
    # otherwise, for two vectors in a single quadrant this computes the cross product area (which is signed)
    # positive sign means a < b, negative sign means b < a
    def quadrant_comp(a,b):
        qa,ia = a
        qb,ib = b
        if qa == qb:
            xa,ya = V[:,ia]
            xb,yb = V[:,ib]
            return xb * ya - yb * xa
        else:
            return qa - qb
    
    quadrant = np.zeros(V.shape[1],dtype=np.int64)
    # get the quadrant of the vector, could be computed using signbits
    def get_quadrant(x,y):
        if x > 0 and y >= 0:
            return 1
        elif x <= 0 and y > 0:
            return 2
        elif x < 0 and y <= 0:
            return 3
        elif x >= 0 and y < 0:
            return 4
    
    # first compute the quadrants
    for idx in range(V.shape[1]):
        quadrant[idx] = get_quadrant(*V[:,idx])

    # store each index with its quadrant. index is used for getting hte vector when the quadrants are the same
    indices_with_quadrants = list(zip(quadrant,range(len(quadrant))))
    
    # run sorted using our comparison operator
    ret = [x[1] for x in sorted(indices_with_quadrants,key=cmp_to_key(quadrant_comp))]


    end = time.time()

    return ret,end-start
    
for N in range(100,20000,100):
    V = np.random.random((2,N)) - .5
    co,ct = cyclic_order(V)
    ao,at = angle_cyclic_order(V)
    print(N,co == ao, ct, at)