如何修正坐标排序函数以正确排列Voronoi区域顶点？

问题背景 #

需要对Voronoi区域的顶点坐标数组combined_coords进行排序，使顶点按围绕区域中心的顺时针/逆时针顺序连接成闭合多边形，但原排序函数输出顺序错误，且仅允许使用numpy和scipy库，禁止调用shapely、geopandas等工具。

原代码问题分析 #

原排序函数的核心问题在于：

• 手动划分象限并计算角度的逻辑错误，导致角度映射混乱
• 使用字典存储索引与角度的映射，匹配时效率低且易出错
• 未处理重复顶点，可能导致排序后出现冗余点

修正后的排序函数 #

import numpy as np

combined_coords = np.array([[ 5766.28476155, 19516.99300136],[ 5765.3326747 , 19516.2217852 ],[ 5764.33255982, 19515.68693966],[ 5762.69492707, 19515.17292775],[ 5762.05045578, 19515.29517553],[ 5762.02505098, 19516.45055273],[ 5762.28121558, 19517.78513446],[ 5762.62958104, 19518.74867786],[ 5763.31238375, 19519.86920443],[ 5763.72620097, 19520.19250031],[ 5764.24999132, 19520.88744217],[ 5764.65547718, 19521.18117486],[ 5765.21676807, 19522.12631202],[ 5765.67501467, 19522.40253271],[ 5766.79878351, 19528.51536924],[ 5766.81357218, 19528.52972979],[ 5766.54317078, 19523.59611998],[ 5766.92157601, 19525.04371133],[ 5767.67457849, 19529.12581027],[ 5771.5263795 , 19524.43240175],[ 5770.59556598, 19522.45791971],[ 5770.45102759, 19521.34643935],[ 5769.91919814, 19521.21760643],[ 5768.52296931, 19520.39572883],[ 5767.63542881, 19519.1100208 ],[ 5767.57293753, 19519.06926975],[ 5766.99422734, 19518.06749945],[ 5766.76994398, 19517.86007797]])

def sorting_function(xy_e):
    # 去除重复顶点（避免浮点误差导致的伪重复）
    xy_unique = np.unique(xy_e.round(decimals=6), axis=0)
    
    # 计算区域中心坐标
    center = np.mean(xy_unique, axis=0)
    
    # 计算每个点相对于中心的极角（弧度），转换为[0, 2π]范围
    angles = np.arctan2(xy_unique[:, 1] - center[1], xy_unique[:, 0] - center[0])
    angles = np.where(angles < 0, angles + 2 * np.pi, angles)
    
    # 按极角从小到大排序（逆时针顺序），需顺时针则取[::-1]
    sorted_indices = np.argsort(angles)
    sorted_coords = xy_unique[sorted_indices]
    
    return sorted_coords.tolist()

new_points = sorting_function(combined_coords)

代码说明 #

1. 去重处理：用np.unique对顶点坐标去重，保留6位小数精度过滤浮点误差导致的伪重复
2. 中心计算：通过所有顶点的均值得到Voronoi区域的中心
3. 极角计算：使用np.arctan2自动处理象限问题，直接计算每个点相对中心的极角，无需手动划分象限
4. 排序逻辑：按极角从小到大排序得到逆时针的多边形顶点顺序，若需要顺时针顺序，只需将结果取反（sorted_coords[::-1].tolist()）

内容的提问来源于stack exchange，提问作者Al_Pacino