按极角排序（Sorting by Polar Angle）

View Original Problem
Table of Contents

在计算几何中，按极角（Polar Angle）排序是一种将二维平面上的点集按照某种旋转顺序进行排列的核心技术。它是构建凸包（Convex Hull）、执行扫描线算法（Sweep Line Algorithm）以及解决可见性问题（Visibility Problems）的基石。

一、 按极角排序

1. 什么是极角？

在平面直角坐标系中，任何非原点的点 都可以用极坐标 表示。

  • (极径): 点 到原点（或参考点）的距离。
  • (极角): 从参考轴（通常是 轴正半轴）逆时针旋转到线段 所经过的角度。

极角排序的核心目标：给定一组点和一个参考点 ，确定这些点相对于 的旋转顺序。

2. 为什么要按极角排序？

在许多几何算法中，我们需要以一种有序的方式处理空间数据，就像在处理一维数组时需要先排序一样。

  • 有序化空间结构：二维空间没有天然的“前后”顺序。极角排序赋予了点集一个“环形”或“扇形”的拓扑顺序。
  • 扫描线的基础：想象雷达扫描，它按照角度变化扫描区域。极角排序本质上就是将点集转化为这种扫描过程中的事件序列。
  • 凸包构建（如Graham扫描法）：凸包的边界点必须按照顺时针或逆时针顺序连接。极角排序直接提供了这种连接的候选顺序。

二、 排序的依据：向量叉积

1. 钟表指针模型

想象参考点是时钟的中心，而其他的点分布在表盘上。极角排序就像是按时间顺序（例如从 3 点钟方向开始逆时针旋转）依次读出这些点。

2. 叉积（Cross Product）作为“方向传感器”

在计算机中直接计算角度（使用 atan2 函数）虽然直观，但涉及浮点数运算，精度较低且速度慢。计算几何中更推崇使用向量叉积。

  • 叉积的几何意义：对于两个向量 和 ，其二维叉积 。
    • 若结果 ： 在 的逆时针方向（左侧）。
    • 若结果 ： 在 的顺时针方向（右侧）。
    • 若结果 ： 与 共线。

这个性质允许我们在不计算实际角度值的情况下，判断两个点的相对顺序。

三、 算法实现

极角排序通常有两种策略：使用 atan2 计算角度，或使用叉积进行比较。以下重点介绍更稳健的叉积法。

步骤 1：确定参考点 (Pivot)

排序必须有一个参照系。

  • 原点作为参考：适用于处理以 为中心的几何问题。
  • 特定点作为参考：在 Graham 扫描法求凸包时，通常选择 坐标最小（若 相同则 最小）的点作为参考点 。这个点一定在凸包上。

步骤 2：坐标变换（相对化）

为了简化计算，将所有点 转化为相对于参考点 的向量 。如果 是原点，此步可省略。

步骤 3：定义比较规则 (Comparator)

这是排序算法的核心。给定两个点 和 （相对于参考点），如何判断谁排在前面？

规则逻辑：

  1. 象限判断：首先判断点所在的象限。例如，如果在 范围内的点应当排在 范围内的点之前。这避免了叉积在跨越 180 度时的歧义。
  2. 利用叉积：如果两点在同一象限（或大致同一半平面），计算叉积 。
    • 如果 ，说明 在 的逆时针方向，故 极角小于 ， 排在前面。
    • 如果 ，说明 在 的顺时针方向，故 极角大于 ， 排在前面。
  3. 共线处理（Tie-breaking）：如果 （即极角相同），通常根据距离参考点的远近排序。
    • 在凸包算法中，通常保留距离较远的点，或者先处理距离近的点（取决于具体算法逻辑）。

伪代码实现 (C++ 风格)

struct Point { double x, y; };

// 计算叉积 (p1-p0) x (p2-p0)
double cross_product(Point p0, Point p1, Point p2) {
    return (p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x);
}

// 距离平方（避免开方，用于共线比较）
double dist_sq(Point p1, Point p2) {
    return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
}

Point pivot; // 全局参考点

// 比较函数
bool compare(Point a, Point b) {
    double cp = cross_product(pivot, a, b);
    if (cp > 0) return true;  // a 在 b 的顺时针方向（相对于pivot），a 排在 b 前面
    if (cp < 0) return false; // a 在 b 的逆时针方向，b 排在 a 前面
    
    // 极角相同，共线情况：距离近的排前面（根据需求调整）
    return dist_sq(pivot, a) < dist_sq(pivot, b);
}

四、 象限问题与 atan2

仅依赖简单的叉积有一个致命的陷阱：叉积只能判断小于 180 度的夹角关系。如果点集分布在参考点的四周（跨越 360 度），直接用叉积比较可能会违反排序的“传递性”（Transitivity），导致排序算法崩溃。

解决方案 A：使用 atan2

atan2(y, x) 返回值的范围是 。

bool compare_atan2(Point a, Point b) {
    return atan2(a.y - pivot.y, a.x - pivot.x) < atan2(b.y - pivot.y, b.x - pivot.x);
}
  • 优点：代码极简，自然处理所有象限。
  • 缺点：浮点误差，且涉及三角函数计算，效率略低。

解决方案 B：分治象限 + 叉积（最佳实践）

将点分为“上半部分”（ 或 ）和“下半部分”。

  1. 如果 和 分属不同部分，上半部分的点优先级高（或低，取决于定义的起始轴）。
  2. 如果 和 同属一部分，则安全地使用叉积比较。

这种方法既保留了整数运算的精度（如果坐标是整数），又解决了跨越 360 度的问题。

五、 边界情况

  1. 参考点重合：如果待排序的点中包含了参考点本身，计算角度或叉积时会出现零向量。通常需要预处理将参考点移除，或者在比较函数中特殊处理（认为其角度最小或最大）。
  2. 精度问题：在使用浮点数坐标时，cross_product 接近 0 但不等于 0 的情况会导致判断错误。必须引入 (epsilon) 容差处理。
  3. 共线点的顺序：
    • 在 Graham Scan 中，如果多个点极角相同，通常只保留距离最远的点，或者按照距离从小到大排序。
    • 但在处理共线边界时（例如凸包的一条边上有多个点），如果排序顺序不当（例如先远后近），会导致算法在栈操作时错误地剔除中间点。

六、 总结

极角排序是从无序的二维点集通向有序几何结构的桥梁。

  • 核心思想：将二维空间位置关系转化为一维的角度序。
  • 关键工具：向量叉积（避免三角函数，保证精度）。
  • 核心难点：处理跨越 180/360 度的拓扑结构以及共线点的退化情况。

掌握极角排序，不仅是学习凸包算法的前提，更是培养将几何直观转化为代数逻辑（Analytic Geometry）能力的关键一步。