1. 项目概述从“找边界”到“Graham Scan”的算法之旅最近在整理一些计算几何的旧代码翻到了当年实现Graham Scan算法找凸包的C程序。凸包这个概念听起来有点学术但说白了它就是一个“找边界”的问题。想象一下你有一堆随机散落在桌面上的图钉现在要用一根橡皮筋去套住它们橡皮筋最后绷紧形成的那个多边形就是这些图钉的“凸包”。这个问题在计算机视觉、地理信息系统、路径规划甚至游戏开发里都特别常见比如确定一个机器人的活动范围、计算一片森林的轮廓或者像有些网络热词里提到的“从多项式到神经网络”的模型边界分析底层都可能用到类似的几何思想。在众多求解凸包的算法里Graham Scan以其**O(n log n)**的时间复杂度脱颖而出成为了经典中的经典。它聪明的地方在于先找到一个“基点”然后把其他点按照相对于这个基点的“极角”排序最后用一个栈来模拟那个收缩的“橡皮筋”一趟扫描就能把凸包上的点按顺序找出来。我这次分享的实现重点就放在“极坐标序”这个排序策略上并用C把它写清楚。你会发现理解了它不仅对凸包问题对很多需要处理二维点集顺序的算法比如一些“贪心算法”的预处理步骤都会很有启发。2. 算法核心思想与极坐标序的奥秘Graham Scan算法的优雅很大程度上源于其清晰的预处理和巧妙的扫描过程。整个算法可以拆解为三个环环相扣的步骤而“极坐标序”是承上启下的关键。2.1 算法三步走定位、排序、扫描第一步寻找基点这不是随便选一个点。算法要求我们找到点集中y坐标最小的点如果有多个y坐标相同的点则取其中x坐标最小的那个。这个点有一个重要的几何性质它一定是最终凸包的一个顶点通常是左下角的顶点。选择y最小次之x最小的点作为基点能保证后续按极角排序时所有点都分布在基点的“上方”或“水平右侧”为单调栈的扫描过程奠定了稳定的基础。我最初实现时曾尝试选x最小的点虽然理论上也可以但在处理某些特殊点集时排序的逻辑会变得稍微复杂一些不如选y最小点来得直观和通用。第二步按极角排序极坐标序这是Graham Scan算法的精髓也是本次实现的重点。所谓“极角”就是以基点为原点计算其他点相对于原点的方位角。我们需要按照这个极角从小到大的顺序对所有点进行排序。极角序带来了一个巨大的好处当我们按这个顺序遍历点时相当于绕着基点逆时针旋转一圈这完美契合了凸包“边界”的遍历方向。但是这里有一个必须处理的细节共线问题。当两个点与基点形成的极角相同时它们与基点是在同一条射线上的。这时该如何排序正确的策略是将距离基点更近的点排在前面。为什么考虑一种极端情况如果有多个点与基点共线那么只有最近的和最远的点可能成为凸包顶点线段的两端中间的点都是冗余的。让近的点先入栈在后续扫描时这些中间的点会因为无法构成“左转”而被弹出栈从而被自然过滤掉。这个处理共线点的技巧是保证算法鲁棒性的关键。第三步栈扫描构建凸包用一个栈通常用vector模拟来维护当前“可能是凸包顶点”的点序列。我们依次将排序后的点压入栈中。每当我们考虑压入一个新点P时我们需要检查栈顶的两个点设为stack[top-1]为Astack[top]为B与新点P构成的向量叉积。计算(B-A) × (P-B)。如果叉积大于0说明从AB到BP是“左转”的这对于逆时针遍历的凸包是符合的可以将P入栈。如果叉积小于等于0说明是“右转”或共线那么当前栈顶的点B就不可能成为凸包顶点它使得多边形“凹”进去了或者多了冗余点需要将B弹出栈然后继续用新的栈顶点进行检查直到满足左转条件或栈中元素少于2个。这个过程就像是用一个活动的窗口在不断修正凸包的边界。2.2 为什么是极坐标序与其他排序方式的对比你可能会问除了极角按其他方式排序行不行比如直接按x坐标、y坐标或者到基点的距离答案是不行或者效率很低。Graham Scan的核心在于其扫描过程利用了极角序带来的“逆时针单调性”。只有按极角排序才能保证当我们用栈扫描时每次检查“左转”性质是局部且正确的算法才能在线性时间内完成。如果按x坐标排序点的遍历顺序是杂乱无章的无法保证栈中维护的点序列始终构成一个“凸”的部分算法就会失效。另一种著名的算法“Andrew算法”或称上下凸壳法采用的是按x坐标和y坐标的字典序排序然后分别求上凸壳和下凸壳。它同样高效O(n log n)且代码可能更简洁因为它避免了计算浮点数的极角。但Graham Scan的极坐标序思想更为直观地体现了“绕着中心点扫描”的几何图像对于理解凸包的形成过程非常有帮助。选择哪种实现有时取决于具体场景和个人偏好。在C的算法竞赛或面试中就像热词里提到的“c面试题”、“手撕算法题目”两种算法都可能被考察。注意浮点数精度问题。计算极角通常需要用到atan2(y, x)函数这会引入浮点数运算和精度误差。在严格比较极角大小时这可能带来问题。一个更稳健的实践是不直接计算和比较极角而是通过叉积来比较。具体来说在排序的比较函数里对于两个点p1和p2我们计算它们相对于基点p0的叉积cross(p0, p1, p2)。如果叉积大于0说明p1在p2的逆时针方向极角更小如果叉积等于0则比较它们到p0的距离。这种方法完全使用整数运算如果坐标是整数彻底避免了精度烦恼是工业级代码的推荐做法。3. C实现详解从理论到代码理解了原理我们来看C实现。我会把代码拆成几个核心函数并解释每一个细节。3.1 数据结构与辅助函数首先我们定义点和一些必要的工具函数。为了清晰我们使用结构体Point。#include iostream #include vector #include algorithm #include cmath #include stack using namespace std; // 定义点结构体 struct Point { double x, y; Point(double x 0, double y 0) : x(x), y(y) {} // 减法运算符重载方便向量运算 Point operator-(const Point other) const { return Point(x - other.x, y - other.y); } // 用于排序时的相等判断注意浮点数误差 bool operator(const Point other) const { return fabs(x - other.x) 1e-9 fabs(y - other.y) 1e-9; } }; // 计算叉积 (p1-p0) x (p2-p0) double cross(const Point p0, const Point p1, const Point p2) { Point a p1 - p0; Point b p2 - p0; return a.x * b.y - a.y * b.x; } // 计算两点距离的平方避免开方用于比较 double distSq(const Point p1, const Point p2) { double dx p1.x - p2.x; double dy p1.y - p2.y; return dx * dx dy * dy; }这里有几个设计考量使用double存储坐标虽然很多OJ题目坐标是整数但使用double更具通用性可以处理更广泛的几何问题。重载减法运算符让向量运算的代码更简洁更接近数学表达。叉积函数cross这是整个算法的“心脏”。它计算的是向量(p0-p1)和(p0-p2)的叉积。结果的正负指示了旋转方向。距离平方distSq在只需要比较距离大小时计算平方值避免了耗时的开方运算是一个常见的优化技巧。3.2 核心实现GrahamScan 类我们将算法封装成一个类这样状态更清晰也便于复用。class GrahamScan { private: vectorPoint points; Point pivot; // 基点 public: GrahamScan(const vectorPoint inputPoints) : points(inputPoints) {} // 主函数返回凸包顶点按逆时针顺序 vectorPoint getConvexHull() { int n points.size(); if (n 3) { // 点数少于3所有点都在凸包上注意共线情况 vectorPoint hull(points.begin(), points.end()); // 对于两点可以按极角排序返回这里简单返回 return hull; } // 1. 寻找基点y最小次之x最小 int pivotIndex 0; for (int i 1; i n; i) { if (points[i].y points[pivotIndex].y || (fabs(points[i].y - points[pivotIndex].y) 1e-9 points[i].x points[pivotIndex].x)) { pivotIndex i; } } // 将基点交换到数组首位方便后续排序 swap(points[0], points[pivotIndex]); pivot points[0]; // 2. 按极角排序使用叉积比较避免atan2 sort(points.begin() 1, points.end(), [this](const Point a, const Point b) { double orient cross(pivot, a, b); if (fabs(orient) 1e-9) { // 极角相同共线 return distSq(pivot, a) distSq(pivot, b); // 近的在前 } return orient 0; // 如果orient0a在b的逆时针方向即a的极角小 }); // 3. 处理排序末尾的共线点重要 // 经过排序与基点共线的点近的在前面远的在后面。 // 我们需要将共线点中距离最远的那个点调整到排序序列的末尾前的位置 // 因为它在扫描时应该最后被处理且近的共线点会被弹出。 // 更常见的做法是排序后单独处理末尾的共线点确保它们按距离降序排列。 // 这里采用一个稳健的方法找到最后一个不与基点共线的点lastNonCollinear int lastNonCollinear n-1; while (lastNonCollinear 0 fabs(cross(pivot, points[lastNonCollinear], points[lastNonCollinear-1])) 1e-9) { lastNonCollinear--; } // 反转最后一段共线点的顺序让最远的点紧接在lastNonCollinear之后 reverse(points.begin() lastNonCollinear, points.end()); // 4. Graham Scan 扫描 vectorPoint hull; hull.push_back(points[0]); hull.push_back(points[1]); hull.push_back(points[2]); for (int i 3; i n; i) { // 当新点使得当前凸包“右转”或“直行”时弹出栈顶 while (hull.size() 2) { Point top hull.back(); hull.pop_back(); Point secondTop hull.back(); // 如果从secondTop-top-points[i]是左转则停止弹出 if (cross(secondTop, top, points[i]) 1e-9) { hull.push_back(top); // 把top放回去 break; } // 否则top被永久弹出继续检查新的栈顶 } hull.push_back(points[i]); } return hull; } };3.3 代码逐段解析与避坑指南1. 基点选择与交换pivotIndex的查找逻辑清晰先比y再比x。找到后与points[0]交换。这一步的交换很重要它让基点固定到数组开头这样排序函数sort只需要对points.begin()1之后的部分排序避免了在比较函数中每次都判断当前点是否是基点。2. 排序比较函数避开浮点极角这是最关键的部分。我们使用了Lambda表达式作为sort的比较器。它接收两个点a和b首先计算cross(pivot, a, b)。如果叉积的绝对值极小小于1e-9我们认为三点共线。此时按到基点的距离平方排序近的在前。为什么近的在前结合后续的扫描逻辑近的点先入栈当远的点要入栈时由于共线且更远近的点会被弹出因为不满足严格的左转最终保留的是最远的点这正是凸包顶点。如果叉积不为零则根据叉积正负决定顺序。orient 0意味着a在b的逆时针方向即a的极角更小应该排在前面。3. 处理末尾共线点一个易错点这是很多初学者包括当年的我容易忽略导致结果错误或遗漏顶点的地方。排序后所有与基点共线的点会聚集在一起。按照我们的比较函数它们是按距离升序排列的近的在前。例如基点P0共线点P1近P2远。排序后顺序是[P0, ..., P1, P2, ...]。 在扫描时我们先压入P0P1。当处理P2时检查(P0, P1, P2)的叉积。由于共线叉积为0不满足 1e-9的左转条件所以P1会被弹出栈然后栈变成[P0]接着压入P2。最终凸包顶点是P0和P2正确过滤了中间点P1。但是如果共线点不止两个呢比如P1, P2, P3依次渐远。排序后是P1, P2, P3。扫描时P1入栈P2准备入栈时发现(P0,P1,P2)共线弹出P1压入P2。然后P3准备入栈检查(P0,P2,P3)共线弹出P2压入P3。最终留下P0和P3。逻辑正确。 那为什么还需要reverse那段代码考虑一种情况共线点出现在排序序列的末尾并且在这些共线点之前还有其他的非共线点。扫描过程可能已经构建了部分凸包当处理到末尾这些按升序排列的共线点时可能会错误地留下一个不是最远的点。为了绝对稳健一种做法是找到最后一个非共线点然后把末尾的共线点序列反转使其按距离降序排列。这样最远的点会先被扫描处理。在我的实现中我保留了这段reverse的逻辑作为更稳健的处理但在许多标准实现和竞赛代码中只要排序比较函数正确处理了共线情况近的在前并且扫描时的判断条件用 0而非 0通常可以省略这一步。我建议初学者加上以加深对过程的理解。4. 扫描循环栈的精妙运用我们用vectorPoint hull模拟栈。初始化时直接压入前三个点前提是n3。然后从第4个点开始遍历。while循环是算法的核心只要栈里至少有2个点就检查栈顶两个点与新点是否构成“右转”。注意判断条件cross(secondTop, top, points[i]) 1e-9。这里使用了一个小的容差值1e-9来应对浮点数误差。如果严格大于0说明是左转保持栈不变跳出循环并压入新点。如果小于等于0在容差范围内说明需要弹出栈顶top然后继续用新的栈顶进行判断。这个过程保证了栈hull中维护的点序列始终构成一个关于当前已处理点的、逆时针的“局部凸包”。实操心得关于“栈”的选用。这里用vector而不用stackint是因为我们需要频繁访问栈顶的第二个元素secondTop。std::stack的接口只允许访问栈顶(top())要访问次栈顶需要先pop()再push()很麻烦。用vector的back()和pop_back()、push_back()来模拟栈操作同时能通过索引随机访问方便得多。这是算法实现中一个很实用的小技巧。4. 完整测试用例与结果分析理论再好跑不通也是白搭。我们来写一个完整的测试程序并用几个典型的点集验证算法。// 打印点集 void printPoints(const vectorPoint points, const string name) { cout name : ; for (const auto p : points) { printf((%.1f, %.1f) , p.x, p.y); } cout endl; } int main() { // 测试用例1常规点集 vectorPoint test1 { {0, 0}, {1, 1}, {2, 2}, {0, 2}, {2, 0}, {1, 0.5}, {0.5, 1.5}, {1.5, 1.5} }; // 测试用例2所有点共线 vectorPoint test2 { {0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4} }; // 测试用例3包含重复点 vectorPoint test3 { {0, 0}, {0, 0}, {1, 1}, {1, 1}, {2, 0} }; // 测试用例4一个大点集随机 vectorPoint test4; srand(time(0)); for (int i 0; i 20; i) { test4.push_back(Point(rand() % 100 / 10.0, rand() % 100 / 10.0)); } vectorvectorPoint allTests {test1, test2, test3, test4}; for (int idx 0; idx allTests.size(); idx) { cout \n 测试用例 idx 1 endl; printPoints(allTests[idx], 输入点集); GrahamScan gs(allTests[idx]); vectorPoint hull gs.getConvexHull(); printPoints(hull, 凸包顶点); cout 凸包顶点数: hull.size() endl; } return 0; }预期输出与分析测试用例1输出凸包顶点应为(0.0, 0.0), (2.0, 0.0), (2.0, 2.0), (0.0, 2.0)。这是一个矩形的四个角点内部的点(1,0.5),(0.5,1.5),(1.5,1.5)被正确过滤。测试用例2所有点共线。凸包应该是这条线段的两端点。我们的算法会返回(0.0, 0.0)和(4.0, 4.0)。注意对于所有点共线的情况Graham Scan返回的凸包是一个退化的情况线段。有些应用可能需要特殊处理这种退化凸包。测试用例3包含重复点。算法应该能处理重复点通常会在排序或扫描过程中将重复点视为共线且距离相等的点最终可能只保留一个。输出可能是(0.0, 0.0), (2.0, 0.0), (1.0, 1.0)取决于基点选择和排序细节。在实际应用中预处理时先对点进行去重是个好习惯。测试用例4随机点集。观察输出所有顶点应该构成一个凸多边形并且所有输入点都在这个多边形内部或边上。可以手动画图验证或者用更简单的方法检查凸包上相邻顶点连线的“左转”性质是否一直保持。5. 常见问题、调试技巧与算法变种即使理解了原理和代码第一次实现时也难免踩坑。这里记录几个我遇到过的问题和解决方法。5.1 浮点数精度导致的无限循环或错误结果这是几何算法中最常见的问题。表现在该弹出栈的点没弹出导致凸包包含了内点。或者错误地弹出了凸包顶点。在判断共线叉积为0时因为精度误差本应相等的值被判断为大于或小于一个极小值。解决方案使用容差Epsilon如同我们在代码中使用的1e-9。所有浮点数相等或与0的比较都应该用fabs(a-b) eps或fabs(a) eps的形式。尽可能使用整数如果问题坐标本身就是整数比如许多算法题那么所有运算叉积、距离平方都可以用整数进行彻底杜绝精度问题。这时比较函数和扫描判断中的容差可以设为0。统一比较逻辑确保排序比较函数和扫描判断函数使用相同的容差逻辑。例如排序时认为fabs(orient) eps是共线那么扫描时cross(...) eps才算左转。逻辑不一致会导致错误。5.2 点集规模过小或特殊情况处理点数少于3我们的实现中如果n3直接返回所有点。对于1个点凸包就是它自己对于2个点凸包是连接它们的线段。但需要注意的是返回的点顺序可能不符合“逆时针”要求。如果后续处理需要严格的逆时针顺序需要对这两种情况做额外处理。所有点共线如上所述算法会返回两个端点。但这是一个退化的凸包线段。调用者需要意识到这一点。去重输入点集中可能有重复点。虽然我们的算法能处理通常只保留一个但重复点会增加不必要的计算。在getConvexHull开头先对points进行去重排序是个好习惯sort(points.begin(), points.end(), [](Point a, Point b){ return a.xb.x || (a.xb.x a.yb.y); });然后使用unique和erase。但要注意去重后要重新检查点数是否仍大于等于3。5.3 算法变种与性能考量Andrews Monotone Chain 算法如前所述这是另一个O(n log n)的算法。它按x坐标次之y坐标排序然后分别构建上凸壳和下凸壳。其优点是完全避免了几何函数如atan2和浮点比较只用叉积且常数因子可能更小。代码同样简洁。在很多场景下它是比Graham Scan更受欢迎的实现。动态凸包如果点集是动态的可以随时增加或删除点需要维护凸包则有更复杂的数据结构如“平衡树”来支持但这不是Graham Scan所擅长的。三维凸包思想可以推广到三维但算法如QuickHull要复杂得多。Graham Scan本质是二维算法。性能分析我们的实现中排序是O(n log n)扫描是O(n)。因此总时间复杂度是O(n log n)。空间复杂度主要是排序所需的O(n)和栈所需的O(h)其中h是凸包顶点数最坏情况下hn所以也是O(n)。5.4 调试与可视化建议几何算法光看输出数字很难调试最好能可视化。打印中间结果在排序后、扫描的每一步打印出当前栈的状态。观察点是如何被压入和弹出的。使用绘图工具用Python的matplotlib或在线绘图工具将输入点、基点和每一步栈中的点连线画出来。这能最直观地看到算法是如何“收紧”橡皮筋的。构造极端测试数据比如所有点在一个圆上、所有点共线、点非常密集、有大量重复点等。这些往往是算法失效的角落案例。最后关于网络热词中提到的“c小游戏”、“游戏开发”凸包可以用于碰撞检测的粗略阶段确定物体的包围区域、视野计算等。而“路径规划”中凸包可以帮助确定一个区域的核心通道或安全区域。理解了这个基础算法就为处理更复杂的几何问题打开了一扇门。实现时把握住“基点-极角序-栈扫描”这个主线仔细处理共线和精度问题就能写出稳健高效的Graham Scan。
