Sorting list of two-dimensional coordinates by clockwise angle using Python?

Question

I have a set of points with x and y coordinates that can be seen in the figure below. The coordinates of the 9 points were stored in a list as follows:

L = [[5,2], [4,1], [3.5,1], [1,2], [2,1], [3,1], [3,3], [4,3] , [2,3]]

The idea is to sort the points clockwise from an origin. In this case, the origin is the point that is colored and that has an arrow that indicates the direction of the ordering. Do not worry about creating methodology to determine the origin because it is already solved.

Thus, after being ordered, the list L should be as follows:

L = [[2,3], [3,3], [4,3], [5,2], [4,1], [3.5,1], [3,1], [2,1], [1,2]]

Note that the x and y coordinates are not changed. What changes is the storage order.

Do you have any idea of an algorithm, script or methodology for this problem in the python language?

Solution 1

With a bit of trigonometry it's not that hard. Maybe you know but the angle between two (normalized) vectors is acos(vec1 * vec2). However this calculates only the projected angle but one could use atan2 to calculate the direction-aware angle.

To this means a function calculating it and then using it as key for sorting would be a good way:

import math

pts = [[2,3], [5,2],[4,1],[3.5,1],[1,2],[2,1],[3,1],[3,3],[4,3]]
origin = [2, 3]
refvec = [0, 1]

def clockwiseangle_and_distance(point):
    # Vector between point and the origin: v = p - o
    vector = [point[0]-origin[0], point[1]-origin[1]]
    # Length of vector: ||v||
    lenvector = math.hypot(vector[0], vector[1])
    # If length is zero there is no angle
    if lenvector == 0:
        return -math.pi, 0
    # Normalize vector: v/||v||
    normalized = [vector[0]/lenvector, vector[1]/lenvector]
    dotprod  = normalized[0]*refvec[0] + normalized[1]*refvec[1]     # x1*x2 + y1*y2
    diffprod = refvec[1]*normalized[0] - refvec[0]*normalized[1]     # x1*y2 - y1*x2
    angle = math.atan2(diffprod, dotprod)
    # Negative angles represent counter-clockwise angles so we need to subtract them 
    # from 2*pi (360 degrees)
    if angle < 0:
        return 2*math.pi+angle, lenvector
    # I return first the angle because that's the primary sorting criterium
    # but if two vectors have the same angle then the shorter distance should come first.
    return angle, lenvector

A sorted run:

>>> sorted(pts, key=clockwiseangle_and_distance)
[[2, 3], [3, 3], [4, 3], [5, 2], [4, 1], [3.5, 1], [3, 1], [2, 1], [1, 2]]

and with a rectangular grid around the origin this works as expected as well:

>>> origin = [2,3]
>>> refvec = [0, 1]
>>> pts = [[1,4],[2,4],[3,4],[1,3],[2,3],[3,3],[1,2],[2,2],[3,2]]
>>> sorted(pts, key=clockwiseangle_and_distance)
[[2, 3], [2, 4], [3, 4], [3, 3], [3, 2], [2, 2], [1, 2], [1, 3], [1, 4]]

even if you change the reference vector:

>>> origin = [2,3]
>>> refvec = [1,0]  # to the right instead of pointing up
>>> pts = [[1,4],[2,4],[3,4],[1,3],[2,3],[3,3],[1,2],[2,2],[3,2]]
>>> sorted(pts, key=clockwiseangle_and_distance)
[[2, 3], [3, 3], [3, 2], [2, 2], [1, 2], [1, 3], [1, 4], [2, 4], [3, 4]]

Thanks @Scott Mermelstein for the better function name and @f5r5e5d for the atan2 suggestion.

Solution 2

this should illustrate the issues, gives a visualization tool

but it doesn't work every time for the getting the correct entry point for a group of points at the same distance

import random
import pylab
import cmath
from itertools import groupby 


pts = [(random.randrange(-5,5), random.randrange(-5,5)) for _ in range(10)]

# for this problem complex numbers are just too good to pass up

z_pts = [ i[0] + 1j*i[1] for i in pts if i != (0, 0)]

z_pts.sort(key = lambda x: abs(x))

gpts = [[*g] for _, g in groupby(z_pts, key = lambda x: abs(x) ) ]
print(*gpts, sep='\n')

spts = [1j/2]

for e in gpts:
    if len(e) > 1:
        se = sorted(e, key = lambda x: cmath.phase(-x / spts[-1]))
        spts += se
    else:
        spts += e

print(spts)

def XsYs(zs):
    xs = [z.real for z in zs]
    ys = [z.imag for z in zs]
    return xs, ys

def SpiralSeg(a, b):
    '''
    construct a clockwise spiral segment connecting
    ordered points a, b specified as complex numbers

    Inputs
        a, b complex numbers
    Output
        list of complex numbers
    '''
    seg = [a]
    if a == 0 or a == b:
        return seg
    # rotation interpolation with complex numbers!
    rot = ( b / a ) ** ( 1 / 30 ) 
    # impose cw rotation direction constraint
    if cmath.phase( b / a ) > 0: # add a halfway point to force long way around
        plr = cmath.polar( b / a )
        plr = (plr[0]**(1/2), plr[1] / 2 - 1 * cmath.pi ) # the rotor/2
        a_b = cmath.rect(*plr) * a   # rotate the start point halfway round   
        return SpiralSeg(a, a_b) + (SpiralSeg(a_b, b))

    for _ in range(30):
        a *= rot 
        seg.append(a)
    return seg  

segs = [SpiralSeg(a, b) for a, b in zip(spts, spts[1:])]

pylab.axes().set_aspect('equal', 'datalim')

pylab.scatter(*XsYs(z_pts))
for seg in segs:
   pylab.plot(*XsYs(seg))

[(1-2j), (-2-1j)]
[(2-3j)]
[(1+4j)]
[(3+3j)]
[(-3-4j), (3-4j), (4-3j)]
[(1-5j)]
[(-4-4j)]
[0.5j, (-2-1j), (1-2j), (2-3j), (1+4j), (3+3j), (-3-4j), (3-4j), (4-3j), (1-5j), (-4-4j)]



[-1j]
[(-1-1j)]
[(-1-2j), (-1+2j), (2+1j)]
[(-4+0j)]
[(1-4j)]
[-5j, (-4-3j)]
[(1-5j)]
[0.5j, -1j, (-1-1j), (-1-2j), (2+1j), (-1+2j), (-4+0j), (1-4j), (-4-3j), -5j, (1-5j)]

Solution 3

Sorting by angle is not enough
We should sort points lexicographicallly by polar angle and distance from origin
We sort by polar angle and in case of a tie we sort by a distance from origin

Comments

[Scott Mermelstein]

At first I had a comment saying "you should sort on lenvector as well as angle", but now that I read more carefully, I see that's what your angle function is doing. Could I suggest a rename of your function? I'd almost call it "rectangular_to_polar", but your system is more useful than polar coordinates would be to this question. Some similar name for your sort function would help avoid confusion, though.

[f5r5e5d]

problems with angle calculations: all angle calcs are mod 2*pi at best; acos wraps at pi, is symmetric about 0; atan2 is better, but still wraps at 2*pi

[MSeifert]

@f5r5e5d You're right, I changed the answer. However atan2 should be good enough to represent all angles between 0 and 360 (or 0 and 2*math.pi).

[f5r5e5d]

but there's no reason to expect an arbitrarily large set data points can be connected by a non intersecting piecewise spiral trace when sorted mod 2* pi by atan2 either - you really need to keep a angle history, wrap the angles past 2*pi by adding multiples of 2*pi

[MSeifert]

@f5r5e5d Do you have an example where my proposed function fails? I've tested several cases and I don't exactly know what do you mean with spiral trace? I think he wants them sorted by clockwise angle (or if that's equal then shortest length first).

[f5r5e5d]

What happens when you have a group of points at the same distance, and the 1st group point by the sorted mod 2 * pi "principle angle" is the "wrong" direction by angle from the previous point prior to the group? On a int grid you can have many such groupings.

[f5r5e5d]

my answer isn't finished but I thought some could use the viz tool

[MSeifert]

@f5r5e5d I actually don't think he wants a spiral, he only mentioned sorting by clockwise angle. But cool images! :-)