高效确定新点在绕中心点顺时针排序点列表中的插入位置

嘿，这个需求我太熟了！之前做图形相关项目时刚好踩过三角函数的坑，完全可以靠向量叉积搞定，根本不需要Math.atan2这类三角函数，既避开了浮点数精度问题，还能提升计算效率。

核心思路：用叉积判断相对方向 #

先明确前提：我们有一个中心点O，以及已经按顺时针绕O排序的点列表points，现在要插入新点Q。

叉积是判断两点相对中心点转向的关键工具：
对于点A和B，计算向量OA = (A.x - O.x, A.y - O.y)，向量OB = (B.x - O.x, B.y - O.y)，叉积公式为：

def cross(O, A, B):
    return (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0])

叉积的符号直接反映方向：

• 若cross(O, A, B) < 0：B在A的顺时针方向（相对于O）
• 若cross(O, A, B) > 0：B在A的逆时针方向（相对于O）
• 若cross(O, A, B) = 0：A、B、O三点共线

因为原列表是顺时针有序的，所以任意相邻点Pi和Pi+1都满足cross(O, Pi, Pi+1) < 0（下一个点在前一个点的顺时针侧）。我们要做的就是找到Q的插入位置，保持这个规律。

具体实现步骤 #

1. 定位插入位置

我们可以遍历列表（大列表推荐用二分查找优化），寻找第一个点Pi，使得cross(O, Pi, Q) > 0——这说明Q在Pi的逆时针侧，应该插在Pi的前面。

如果遍历完所有点，所有cross(O, Pi, Q) <= 0，说明Q在所有点的顺时针侧，直接插在列表末尾即可。

2. 处理共线情况

如果遇到cross(O, Pi, Q) = 0（三点共线），需要用点积判断Q的位置：

def dot(O, A, B):
    return (A[0] - O[0]) * (B[0] - O[0]) + (A[1] - O[1]) * (B[1] - O[1])

• 若dot(O, Pi, Q) > 0：Q和Pi在O的同一侧，可根据需求按距离O的远近排序（比如离O远的在前）
• 若dot(O, Pi, Q) < 0：Q在O的另一侧，通常插在列表的另一端（比如原列表都是O右侧的点，Q在左侧就插在开头）

示例代码（Python） #

def cross(O, A, B):
    return (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0])

def insert_clockwise(O, points, Q):
    n = len(points)
    # 处理空列表
    if n == 0:
        return [Q]
    # 检查是否插在开头
    if cross(O, points[0], Q) > 0:
        return [Q] + points
    # 检查是否插在末尾
    if cross(O, points[-1], Q) < 0:
        return points + [Q]
    # 遍历找插入位置（大列表可替换为二分查找）
    for i in range(n):
        if cross(O, points[i], Q) > 0:
            return points[:i] + [Q] + points[i:]
    # 兜底（理论上不会执行到）
    return points + [Q]

方案优势 #

• 无精度问题：叉积和点积都是整数运算（坐标为整数时），彻底避开三角函数的浮点数误差
• 效率更高：遍历是O(n)，二分查找可优化到O(logn)，比计算角度再排序快得多
• 逻辑直观：直接基于几何方向判断，不需要理解角度计算的复杂转换

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