Sorting according to clockwise point coordinates
# 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
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]
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)]
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]