翼型闭环非凸点云顺时针排序问题及现有实现优化需求

问题背景 #

需对构成翼型形状闭环的非凸点云进行顺时针排序，该点云并非随机点，已有一定顺序但闭环不保证凸性。现有分组排序方法（先按固定数量分组，组内按组重心角度排序，再按全局重心角度排序分组）在部分场景下效果异常，原实现代码如下：

import numpy as np

def sort_clockwise_full(Array, format_output = "numpy"):

    Array = np.array(Array)
    n = 5
    aux_lst = []
    
    CGX_global = np.mean(Array[:,0])
    CGY_global = np.mean(Array[:,1])

    for i in range(int(len(Array)/n)):

        # breaks the array in n parts
        try:
            aux_arr = Array[n*i:n*(i+1),:]
        except IndexError:
            aux_arr = Array[n*i+n:,:]

        # calculates these parts' CoG
        COG_x = np.mean(aux_arr[:,0])
        COG_y = np.mean(aux_arr[:,1])

        # calculates the angle of each point w.r.t. the CoG of this part
        angles = np.arctan2((aux_arr[:,1] - COG_y),(aux_arr[:,0] - COG_x))
        angles = np.array(angles).reshape((aux_arr.shape[0], 1))*180/np.pi

        # sorts the full_aux_arr according to this angle 
        full_aux_arr = np.concatenate((aux_arr, angles),axis = 1)
        full_aux_arr = full_aux_arr[full_aux_arr[:, 2].argsort()][:,0:2]

        # calculates each part's CoG angle w.r.t. global CoG
        CG_angle = np.arctan2((COG_y - CGY_global),(COG_x - CGX_global))
        aux_lst.append([full_aux_arr, CG_angle])
  
    # sorts the parts according to each part's CoG angle w.r.t. global CoG
    idxs_lst = np.array([i[1] for i in aux_lst]).argsort()
    aux_lst_sorted = [aux_lst[i] for i in idxs_lst]
    
    # writes sorted points to end_arr
    end_arr = []
    for points in aux_lst_sorted:
        for point in points[0]:
            end_arr.append(point)
    end_arr = np.array(end_arr)

    return end_arr

原方法异常原因分析 #

1. 分组逻辑bug：当点云总数无法被固定分组数n=5整除时，异常处理块错误跳过剩余点（Array[n*i+n:,:]会取空数组），导致部分点丢失，破坏闭环完整性。
2. 硬切分组不合理：按原始顺序固定数量分组，未考虑点的空间分布，可能将翼型不同区域（如上下表面、前后缘）的点混分到同一组，组重心计算偏差导致角度排序混乱。
3. 组内排序逻辑缺陷：仅依赖组重心的极角排序，当组内点跨多个象限或组本身非凸时，会打乱点的连续空间关系，导致局部顺序错乱。
4. 组间衔接无约束：仅按组重心的全局极角排序分组，未考虑组与组之间的点空间连续性，容易出现分组跳转，破坏闭环平滑性。

优化方案：全局极角排序+非凸区域修正 #

针对翼型闭环的特性，采用全局重心极角排序+邻域微调的方案，既保证整体顺时针方向，又修复非凸区域的局部错乱：

优化思路 #

1. 计算全局重心，以全局重心为原点计算每个点的极角（转换为顺时针方向定义）。
2. 按极角对所有点进行初步排序，保证整体方向正确。
3. 针对翼型非凸区域（如前后缘），通过邻域搜索修正局部点的顺序，保证相邻点的空间连续性。
4. 自适应选择翼型前缘（最左点）作为起始点，符合翼型结构特性。

优化后代码 #

import numpy as np
from scipy.spatial import KDTree

def sort_airfoil_clockwise(points):
    points = np.array(points)
    if len(points) < 3:
        return points
    
    # 计算全局重心
    cog = np.mean(points, axis=0)
    # 计算每个点相对于重心的极角，转换为顺时针角度（0~2π）
    angles = np.arctan2(points[:, 1] - cog[1], points[:, 0] - cog[0])
    clockwise_angles = (2 * np.pi - angles) % (2 * np.pi)
    
    # 按顺时针角度初步排序
    sorted_idxs = np.argsort(clockwise_angles)
    sorted_points = points[sorted_idxs]
    
    # 构建KD树用于邻域搜索，修正非凸区域的局部顺序
    kdtree = KDTree(sorted_points)
    corrected_idxs = [0]
    remaining_idxs = set(range(len(sorted_points)))
    remaining_idxs.remove(0)
    
    for _ in range(len(sorted_points)-1):
        current_idx = corrected_idxs[-1]
        # 搜索最近的未访问点（取前5个最近点，避免局部最优）
        distances, neighbors = kdtree.query(sorted_points[current_idx], k=5)
        for neighbor in neighbors:
            if neighbor in remaining_idxs:
                corrected_idxs.append(neighbor)
                remaining_idxs.remove(neighbor)
                break
    
    # 生成初步修正后的点云
    final_points = sorted_points[corrected_idxs]
    
    # 验证闭环首尾连续性，若不连续则调整起始点为翼型前缘（最左点）
    avg_step = np.mean(np.linalg.norm(np.diff(final_points, axis=0), axis=1))
    if np.linalg.norm(final_points[0] - final_points[-1]) > avg_step * 2:
        start_idx = np.argmin(final_points[:, 0])
        final_points = np.concatenate([final_points[start_idx:], final_points[:start_idx]])
    
    return final_points

方案优势 #

• 全局角度保证顺时针方向：基于全局重心的极角排序确保整体方向正确，避免分组导致的全局混乱。
• 邻域搜索修正局部错乱：针对翼型非凸区域，通过最近邻搜索保证点的连续空间关系，修复局部顺序异常。
• 自适应起始点：以翼型前缘（最左点）作为起始点，符合翼型结构特性，保证闭环合理性。

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