凸多边形顶点顺/逆时针排序：角度计算错误排查及算法咨询

原代码核心问题 #

你使用的atan((m1-m2)/(1+m1m2))是计算两条直线的夹角，而非顶点相对于平均点的极角。这个公式只能返回0-90度的夹角范围，无法区分方向（比如左右、上下象限），直接导致排序逻辑完全错误。此外，依赖斜率计算还会遇到x坐标相等时（垂直直线）分母为0的报错风险。

修正方案：极角排序（推荐） #

直接计算每个顶点相对于平均点的向量极角，使用math.atan2(dy, dx)替代atan——这个函数能根据向量的x、y差值自动判断象限，返回正确的角度范围（-π到π弧度），完美适配顺时针/逆时针排序需求。

修正后的代码 #

import math

def sort_polygon_vertices(polygon, clockwise=False):
    # 计算多边形顶点的平均点
    x_coords, y_coords = zip(*polygon)
    x_avg = sum(x_coords) / len(x_coords)
    y_avg = sum(y_coords) / len(y_coords)
    
    # 计算单个顶点相对平均点的极角（转换为0-2π范围）
    def get_polar_angle(vertex):
        dx = vertex[0] - x_avg
        dy = vertex[1] - y_avg
        angle = math.atan2(dy, dx)
        # 将负角度转换为0-2π的正角度，避免排序混乱
        return angle + 2 * math.pi if angle < 0 else angle
    
    # 按极角排序，clockwise参数控制顺时针/逆时针
    sorted_vertices = sorted(polygon, key=get_polar_angle)
    if clockwise:
        sorted_vertices.reverse()
    
    return sorted_vertices

# 测试示例
polygon = [[1, 5], [4, 1], [7, 8], [7, 1], [1.8, 5.4]]
counter_clockwise_result = sort_polygon_vertices(polygon)
clockwise_result = sort_polygon_vertices(polygon, clockwise=True)

print("逆时针排序结果:", counter_clockwise_result)
print("顺时针排序结果:", clockwise_result)

代码说明 #

• 极角计算：atan2(dy, dx)直接接收向量的y差、x差作为参数，自动处理所有象限的角度计算，不会出现斜率法的分母为0问题。
• 角度范围转换：将-π到π的弧度转换为0到2π的正角度，确保排序时角度的连续性。
• 双向排序控制：通过clockwise参数切换排序方向，反转排序结果即可实现顺时针排列。

其他可行排序算法 #

如果处理的是简单不自交多边形，还可以选择以下方法：

• 凸包基准排序：先找到多边形最左下角的顶点，再以该点为基准计算其他顶点的极角排序，适合凸多边形场景。
• 叉积方向排序：通过计算相邻顶点的叉积判断转向，调整顶点顺序，但实现复杂度高于极角排序，适合特定场景。

内容的提问来源于stack exchange，提问作者Jahid Chowdhury Choton