Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Sorting according to clockwise point coordinates

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

like image 906
john doe Avatar asked Jun 28 '18 04:06

john doe


People also ask

How do you determine whether a polygon's points go in a clockwise or counter clockwise direction?

Orientation of a simple polygonIf the determinant is negative, then the polygon is oriented clockwise. If the determinant is positive, the polygon is oriented counterclockwise. The determinant is non-zero if points A, B, and C are non-collinear.

How do you sort vertices of a polygon in counter clockwise order?

By choosing an arbitrary (x, y) pair as your "center", you can compute the polar angle of each point relative to your center, and then sort them based on this angle. The end result sorts the polygon's point in clockwise/counterclockwise direction.

How do you sort XY coordinates in Python?

my_updated_list = sorted(my_list , key=lambda k: [k[1], k[0]]), you have to assign that to new variable. @LipingHuang That is exactly what this method does. See Antti's comment. If you wanted it the other way around, swap k[1] with k[0].


3 Answers

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)]
like image 170
blhsing Avatar answered Oct 01 '22 10:10

blhsing


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)]
like image 30
Wolfgang Fahl Avatar answered Oct 01 '22 09:10

Wolfgang Fahl


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]
like image 35
BERA Avatar answered Oct 01 '22 09:10

BERA