将二维点集按顺时针排序

1. 简介

设想我们有一组分布在二维平面上的点，想要将它们连接起来形成一个闭合图形。要实现这个目标，第一步就是对这些点进行排序。

在本文中，我们将介绍一种将二维点集按顺时针顺序排序的方法。这种方法适用于围绕一个中心点进行排序的场景，中心点可以是原点，也可以是任意指定的点。我们将以点集的均值作为中心点进行排序。

2. 问题描述

目标：给定一组二维点（每个点由 x 和 y 坐标表示），将这些点按顺时针顺序排序。

我们需要围绕一个中心点来观察这些点。这个中心点可以是原点 (0, 0)，也可以是任意其他点。在本文中，我们采用点集的均值作为中心点：

center_x = sum(x_i) / n
center_y = sum(y_i) / n

需要注意的是，我们并不是在计算凸包（convex hull），而是希望找到一条穿过所有点的闭合路径。如下图所示，即使点分布不规则，只要能形成闭合路径即可接受：

SP-1

与之对比，如果计算凸包，只会保留外围的点，例如下面的图中只保留了点 1、2、3 和 5：

SP 3

此外，我们不处理所有点共线的极端情况。

3. 算法思路

以一组点 a, b, c, d, e, f 为例，如下图所示：

SP 4

3.1 步骤概览

计算中心点：将所有点的 x 和 y 坐标求和后取平均。
平移坐标系：将所有点相对于中心点平移，使中心点位于原点 (0, 0)。
计算角度：使用 atan2(y, x) 计算每个点相对于中心点的角度。
排序逻辑：
- 角度小的点排在前面（顺时针方向）。
- 如果角度相同，距离中心点近的点排在前面。
恢复坐标系：将排序后的点重新平移回原坐标系。

3.2 示例说明

以下图为例：

SP 7

点 e 在第四象限，角度最大，排在第一位。
点 f 在第三象限，角度次之，排在第二位。
点 b 和 a 在第二象限，但 b 更靠近 π，所以排在 a 前面。
点 c 和 d 在第一象限，角度相同，按距离排序，c 更近，排在 d 前面。

最终排序顺序为：e, f, b, a, c, d

SP 8

4. 算法流程图

4.1 总体流程图

graph TD
    A[输入点集] --> B[计算中心点]
    B --> C[将所有点平移至中心点为原点]
    C --> D[调用排序算法]
    D --> E[恢复点集坐标]
    E --> F[输出排序结果]

4.2 比较函数流程图

graph TD
    G[比较两个点 pt1 和 pt2] --> H[计算 pt1 和 pt2 的角度]
    H --> I{pt1_angle < pt2_angle ?}
    I -->|是| J[pt1 排在前面]
    I -->|否| K[比较距离]
    K --> L{pt1_distance < pt2_distance ?}
    L -->|是| M[pt1 排在前面]
    L -->|否| N[pt2 排在前面]

5. 伪代码实现

5.1 主排序算法

algorithm sortPointsCW(Points):
    // INPUT
    //    Points = 一组二维点
    // OUTPUT
    //    按顺时针顺序排序后的点集

    pt_center <- (0, 0)
    for pt in Points:
        pt_center.x += pt.x
        pt_center.y += pt.y

    n <- 点的数量

    pt_center.x /= n
    pt_center.y /= n

    for pt in Points:
        pt.x -= pt_center.x
        pt.y -= pt_center.y

    sort Points using comparePoints function

    for pt in Points:
        pt.x += pt_center.x
        pt.y += pt_center.y

    return Points

5.2 比较函数

function comparePoints(pt1, pt2):
    // INPUT
    //    pt1, pt2 = 要比较的两个点（已平移至原点）
    // OUTPUT
    //    若 pt1 应该在 pt2 前面则返回 true

    angle1 <- getAngle(pt1)
    angle2 <- getAngle(pt2)

    if angle1 < angle2:
        return true

    if angle1 == angle2:
        d1 <- getDistance(pt1)
        d2 <- getDistance(pt2)
        if d1 < d2:
            return true

    return false

5.3 计算角度

function getAngle(pt):
    // INPUT
    //    pt = 当前点
    // OUTPUT
    //    返回从 x 轴正方向顺时针旋转到该点的角度 (0~2π)

    x <- pt.x
    y <- pt.y

    angle <- atan2(y, x)

    if angle < 0:
        angle += 2 * π

    return angle

5.4 计算距离

function getDistance(pt):
    // INPUT
    //    pt = 当前点
    // OUTPUT
    //    返回该点到原点的欧氏距离

    return sqrt(pt.x^2 + pt.y^2)

✅ 优化提示：在比较距离时，可以只比较平方距离，避免开平方运算，提升性能。

6. 算法复杂度分析

6.1 时间复杂度

中心点计算：✅ O(n)
平移操作：✅ O(n)
排序操作：取决于排序算法，若使用快排，则为 ✅ O(n log n)
总体时间复杂度：✅ O(n log n)

6.2 空间复杂度

仅需常量空间存储中心点坐标，✅ O(1)

7. 小结

本文介绍了一种将二维点集按顺时针顺序排序的通用方法。核心思想是：

以点集均值为参考中心点
将点集平移至以中心点为原点
使用角度和距离作为排序依据
使用任意排序算法完成排序
最后将点集恢复至原坐标系

该方法简单、直观，适用于图形绘制、路径规划等需要闭合路径的场景。

⚠️ 踩坑提醒：注意 atan2 返回的是 [-π, π]，需转换为 [0, 2π] 才能正确排序。
✅ 推荐优化：在比较距离时使用平方距离，避免不必要的开平方运算。

Persistence

REST

Security