Sort vertices of a convex polygon in clockwise or counter-clockwise

userpyga1 0
Viewed 54

I am trying to sort the vertices of a polygon in either clockwise or anti-clockwise manner. I am trying to calculate an average point [x_avg, y_avg] inside the polygon and calculate all the angles of the vertices from the average point. But my code is giving wrong angles. I am using the formula "atan((m1-m2)/1+m1m2))" to calculate the relative angle between the average point and any vertice. Please let me know what is wrong with the code? Or what algorithm can I use to calculate the ordered vertices? Here is the code:

import math

def rounding_polygon(polygon):
    x, y = zip(*polygon)
    print(x,y)
    x_avg = sum(x)/len(x)
    y_avg = sum(y)/len(y)
    angles = []
    print('x_a = ', x_avg, 'ya =', y_avg)
    x1, y1 = polygon[0][0], polygon[0][1]
    m_com = (y_avg-y1)/(x_avg-x1)
    for v in polygon:
        x2, y2 = v[0], v[1]
        m_curr = (y_avg-y2)/(x_avg-x2)
        slope = (m_com-m_curr)/(1 + (m_com*m_curr))
        curr_angle = math.degrees(math.atan(slope))
        angles.append([curr_angle, v])
    angles = sorted(angles)
    vertices = [x[1] for x in angles]
    print('angles = ', angles)
    print('vertices = ', vertices)
    return vertices

polygon = [[1, 5], [4, 1], [7, 8], [7, 1], [1.8, 5.4]]
vertices = rounding_polygon(polygon)

print(vertices)
polygon math geometry python-3.x python
1 Answers

atan function gives results in limited range (half of circle). To get full angle range -Pi..Pi, you should use atan2 function that takes two arguments - y-difference and x-difference.

Example uses the lowest (left one if two points have the same Y) point as base for sorting.

import math

polygon = [[1, 5], [4, 1], [7, 8], [7, 1], [1.8, 5.4]]
lowest = min(polygon, key = lambda x: (x[1], x[0]))

vertices = sorted(polygon, key=lambda x: math.atan2(x[1]-lowest[1], x[0]-lowest[0]) + 2 * math.pi)

print(vertices)

>>[[4, 1], [7, 1], [7, 8], [1.8, 5.4], [1, 5]]

Why is the lowest point chosen? To exclude non-transitivity during comparing point direction angles (when A>B, B>C but C>B)

MBo0
Related