Sorting according to clockwise point coordinates

Question

Given a list in Python containing 8 x, y coordinate values (all positive) of 4 points as [x1, x2, x3, x4, y1, y2, y3, y4] ((xi, yi) are x and y coordinates of ith point ),

How can I sort it such that new list [a1, a2, a3, a4, b1, b2, b3, b4] is such that coordinates (ai, bi) of 1 2 3 4 are clockwise in order with 1 closest to origin of xy plane, i.e. something like

          2--------3
          |        |
          |        |
          |        |
          1--------4

Points will roughly form a parallelogram.

Currently, I am thinking of finding point with least value of (x+y) as 1, then 2 by the point with least x in remaining coordinates, 3 by largest value of (x + y) and 4 as the remaining point

Buddie

Get the atan2 from the center. – Fie

@IgnacioVazquez-Abrams That's a good idea – Buddie

There is no need to directly compute angles. Simply sort them using the sign of the 2D cross-product as the comparator. – Diphyodont

@Diphyodont That would work too, but would not be as efficient as computing angles because using the sign of the 2D cross-product means having using a cmp function to compare two coordinates in the list at a time. Computing the angles means we can use them as comparative values for the key parameter, which is much more efficient. See Why is the cmp parameter removed from sort/sorted in Python3.0? – Areca

@Diphyodont On second thought that actually won't work, since for every coordinate on the list there's always another coordinate whose vector to the centroid is clockwise to that of the said coordinate, so there will be no "bottom" to the comparison. In OP's case, we need -135 degrees to be the "bottom" of the sorted list of coordinates. The sign of the 2D cross-product can only help determine if one vector is clockwise to another but cannot help establish how far away from the "bottom" (i.e. -135 degrees) a vector is. – Areca

@Areca it would work but the resultant order of points won't be unique (dependent on the initial arrangement) - to achieve the desired order convention only requires a rotation of the array; but thanks for the heads-up on cmp vs key. – Diphyodont

@Diphyodont I'm not too sure what you mean exactly by uniqueness of point order and rotation of the array (would love to see some pseudo code of your logic), but I just realized also that for two vectors that are in opposite directions, the cross-product will be zero (with no sign), the same as that of two vectors in the same direction, so we won't be able to sort these two set of vectors using cross-product. – Areca

Answer 1

You should use a list of 2-item tuples as your data structure to represent a variable number of coordinates in a meaningful way.

from functools import reduce
import operator
import math
coords = [(0, 1), (1, 0), (1, 1), (0, 0)]
center = tuple(map(operator.truediv, reduce(lambda x, y: map(operator.add, x, y), coords), [len(coords)] * 2))
print(sorted(coords, key=lambda coord: (-135 - math.degrees(math.atan2(*tuple(map(operator.sub, coord, center))[::-1]))) % 360))

This outputs:

[(0, 0), (0, 1), (1, 1), (1, 0)]

Areca

could you please explain this solution? – Forfend

Is there a reason to convert to degress? It seems to add quite a lot of complexity. – Ecru

The order of the following four points is calculated incorrectly "[[408, 455], [464, 722], [872, 636], [816, 370]]" – Osborn

Answer 2

import math

def centeroidpython(data):
    x, y = zip(*data)
    l = len(x)
    return sum(x) / l, sum(y) / l

xy = [405952.0, 408139.0, 407978.0, 405978.0, 6754659.0, 6752257.0, 6754740.0, 6752378.0]
xy_pairs = list(zip(xy[:int(len(xy)/2)], xy[int(len(xy)/2):]))

centroid_x, centroid_y = centeroidpython(xy_pairs)
xy_sorted = sorted(xy_pairs, key = lambda x: math.atan2((x[1]-centroid_y),(x[0]-centroid_x)))
xy_sorted_x_first_then_y = [coord for pair in list(zip(*xy_sorted)) for coord in pair]

Occiput

Answer 3

# P4=8,10 P1=3,5   P2=8,5   P3=3,10
points=[8,3,8,3,10,5,5,10]
k=0
#we know these numbers are extreme and data won't be bigger than these
xmin=1000
xmax=-1000
ymin=1000
ymax=-1000
#finding min and max values of x and y
for i in points:
    if  k<4:
        if (xmin>i): xmin=i
        if (xmax<i): xmax=i        
    else:
        if (ymin>i): ymin=i
        if (ymax<i): ymax=i        
    k +=1

sortedlist=[xmin,xmin,xmax,xmax,ymin,ymax,ymax,ymin]
print(sortedlist)

output:[3, 3, 8, 8, 5, 10, 10, 5] for other regions you need to change sortedlist line. if center is inside the box then it will require more condition controlling

Eichler

Answer 4

What we want to sort by is the angle from the start coordinate. I've used numpy here to interpret each vector from the starting coordinate as a complex number, for which there is an easy way of computing the angle (counterclockwise along the unit sphere)

def angle_with_start(coord, start):
    vec = coord - start
    return np.angle(np.complex(vec[0], vec[1]))

Full code:

import itertools
import numpy as np


def angle_with_start(coord, start):
    vec = coord - start
    return np.angle(np.complex(vec[0], vec[1]))


def sort_clockwise(points):
    # convert into a coordinate system
    # (1, 1, 1, 2) -> (1, 1), (1, 2)
    coords = [np.array([points[i], points[i+4]]) for i in range(len(points) // 2)]

    # find the point closest to the origin,
    # this becomes our starting point
    coords = sorted(coords, key=lambda coord: np.linalg.norm(coord))
    start = coords[0]
    rest = coords[1:]

    # sort the remaining coordinates by angle
    # with reverse=True because we want to sort by clockwise angle
    rest = sorted(rest, key=lambda coord: angle_with_start(coord, start), reverse=True)

    # our first coordinate should be our starting point
    rest.insert(0, start)
    # convert into the proper coordinate format
    # (1, 1), (1, 2) -> (1, 1, 1, 2)
    return list(itertools.chain.from_iterable(zip(*rest)))

Behavior on some sample inputs:

In [1]: a
Out[1]: [1, 1, 2, 2, 1, 2, 1, 2]

In [2]: sort_clockwise(a)
Out[2]: [1, 1, 2, 2, 1, 2, 2, 1]

In [3]: b
Out[3]: [1, 2, 0, 2, 1, 2, 3, 1]

In [4]: sort_clockwise(b)
Out[4]: [1, 0, 2, 2, 1, 3, 2, 1]

Sticky

Answer 5

Based on BERA's answer but as a class:

code

import math

def class Sorter:
    @staticmethod    
    def centerXY(xylist):
        x, y = zip(*xylist)
        l = len(x)
        return sum(x) / l, sum(y) / l  

    @staticmethod    
    def sortPoints(xylist):  
        cx, cy = Sorter.centerXY(xylist)
        xy_sorted = sorted(xylist, key = lambda x: math.atan2((x[1]-cy),(x[0]-cx)))
        return xy_sorted

test

def test_SortPoints():
    points=[(0,0),(0,1),(1,1),(1,0)]
    center=Sorter.centerXY(points)
    assert center==(0.5,0.5)
    sortedPoints=Sorter.sortPoints(points)
    assert sortedPoints==[(0, 0), (1, 0), (1, 1), (0, 1)]

Dinosaurian

Answer 6

As suggested by IgnacioVazquez-Abrams, we can also do sorting according to atan2 angles:

Code:

import math
import copy
import matplotlib.pyplot as plt

a = [2, 4, 5, 1, 0.5, 4, 0, 4]
print(a)


def clock(a):
    angles = []
    (x0, y0) = ((a[0]+a[1]+a[2]+a[3])/4, (a[4]+ a[5] + a[6] + a[7])/4)  # centroid
    for j in range(4):
        (dx, dy) = (a[j] - x0, a[j+4] - y0)
        angles.append(math.degrees(math.atan2(float(dy), float(dx))))
    for k in range(4):
        angles.append(angles[k] + 800)
    # print(angles)

    z = [copy.copy(x) for (y,x) in sorted(zip(angles,a), key=lambda pair: pair[0])]
    print("z is: ", z)

plt.scatter(a[:4], a[4:8])
plt.show()

clock(a)

Output is :

[2, 4, 5, 1, 0.5, 4, 0, 4]
[-121.60750224624891, 61.92751306414704, -46.73570458892839, 136.8476102659946, 678.3924977537511, 861.9275130641471, 753.2642954110717, 936.8476102659946]
z is:  [2, 5, 4, 1, 0.5, 0, 4, 4]

Buddie

Answer 7

Try this line of code

def sort_clockwise(pts):
    rect = np.zeros((4, 2), dtype="float32")
    s = pts.sum(axis=1)
    rect[0] = pts[np.argmin(s)]
    rect[2] = pts[np.argmax(s)]
    diff = np.diff(pts, axis=1)
    rect[1] = pts[np.argmin(diff)]
    rect[3] = pts[np.argmax(diff)]
    return rect

Phonograph