go语言：实现graham scan葛立恒扫描法算法（附带源码）
项目背景详细介绍
在计算几何（Computational Geometry）领域中，**凸包（Convex Hull）**是一个极其基础、同时又非常核心的问题。
简单来说，给定平面上的一组点，凸包就是：
能够包住所有点的、最小的凸多边形
直观理解：
- 想象在桌面上撒一把钉子
- 用一根橡皮筋把所有钉子圈起来
- 橡皮筋形成的形状，就是这些点的凸包
凸包在工程与科研中有大量实际应用，例如：
- 计算机图形学（碰撞检测、可视区域）
- GIS / 地图系统（区域边界计算）
- 图像处理（目标轮廓提取）
- 机器人路径规划
- 模式识别与机器学习
- 游戏引擎中的物理系统
在众多凸包算法中，**Graham Scan（葛立恒扫描法）**是：
- 最经典
- 最适合教学
- 数学与工程结合度极高
的一种算法。
它由 Ronald Graham 在 1972 年提出，是第一个时间复杂度达到 O(n log n) 的凸包算法，至今仍是计算几何入门必学内容。
项目需求详细介绍
本项目的目标是：
使用 Go 语言完整实现 Graham Scan（葛立恒扫描法）算法，计算二维平面点集的凸包。
具体需求如下：
- 功能需求
- 输入：二维平面上的一组点
(x, y) - 输出：按逆时针顺序排列的凸包顶点集合
- 支持任意数量的点（≥ 3）
- 输入：二维平面上的一组点
- 算法要求
- 严格遵循 Graham Scan 算法流程
- 使用叉积判断转向（左转 / 右转）
- 正确处理共线点情况
- 工程要求
- 使用 Go 标准库
- 结构清晰、注释完整
- 算法步骤清晰可追踪
- 教学要求
- 明确解释几何意义
- 每一步都有直觉说明
- 便于板书推导与代码对照
相关技术详细介绍
1. 二维点的表示
在 Go 中，二维点通常用结构体表示：
type Point struct { X int Y int }
使用整数而非浮点数的好处是：
- 避免精度误差
- 叉积计算更安全
- 教学更直观
2. 向量叉积（Cross Product）
Graham Scan 的核心判断依据是向量叉积的符号。
给定三个点 O, A, B，定义向量：
OA = A - O OB = B - O
叉积（二维）结果：
cross = OA.x * OB.y - OA.y * OB.x
含义：
cross > 0：左转（逆时针）cross < 0：右转（顺时针）cross = 0：共线
3. 极角排序（Polar Angle Sort）
Graham Scan 的第一步是：
选一个基准点，然后按极角排序所有其他点
排序规则：
- 极角从小到大（逆时针）
- 极角相同，距离基准点近的在前
实现思路详细介绍
Graham Scan 的整体流程可以概括为四个步骤：
步骤一：选择基准点（Pivot）
从所有点中选出：
- Y 最小
- 若 Y 相同，取 X 最小
该点必然是凸包上的点，用作极角计算的参考。
步骤二：按极角排序
将除基准点外的所有点，按照它们与基准点形成的极角排序。
目的：
- 保证我们是逆时针扫描点集
步骤三：扫描并维护栈
维护一个“栈”（slice）：
- 先压入前两个点
- 从第三个点开始：
- 若出现 右转或共线
- 弹出栈顶
- 直到形成左转
- 当前点入栈
步骤四：栈中剩余点即为凸包
扫描结束后，栈中点：
- 按逆时针顺序
- 正好构成凸包边界
完整实现代码
// ========================================== // 文件名：main.go // 功能：使用 Graham Scan 算法计算二维点集的凸包 // ========================================== package main import ( "fmt" "sort" ) // Point 表示二维平面中的一个点 type Point struct { X int Y int } // cross 计算向量 OA 和 OB 的叉积 // O 为公共起点 func cross(o, a, b Point) int { return (a.X-o.X)*(b.Y-o.Y) - (a.Y-o.Y)*(b.X-o.X) } // distanceSquare 计算两点间距离的平方 // 用于极角相同情况下的排序 func distanceSquare(a, b Point) int { dx := a.X - b.X dy := a.Y - b.Y return dx*dx + dy*dy } // GrahamScan 计算点集的凸包 func GrahamScan(points []Point) []Point { n := len(points) if n <= 3 { return points } // 1. 找到基准点：Y 最小，若相同取 X 最小 pivot := 0 for i := 1; i < n; i++ { if points[i].Y < points[pivot].Y || (points[i].Y == points[pivot].Y && points[i].X < points[pivot].X) { pivot = i } } // 将基准点放到第一个位置 points[0], points[pivot] = points[pivot], points[0] base := points[0] // 2. 按极角排序 sort.Slice(points[1:], func(i, j int) bool { p1 := points[i+1] p2 := points[j+1] c := cross(base, p1, p2) if c == 0 { return distanceSquare(base, p1) < distanceSquare(base, p2) } return c > 0 }) // 3. 使用栈扫描 stack := make([]Point, 0) stack = append(stack, points[0], points[1]) for i := 2; i < n; i++ { for len(stack) >= 2 { top := stack[len(stack)-1] nextToTop := stack[len(stack)-2] if cross(nextToTop, top, points[i]) > 0 { break } stack = stack[:len(stack)-1] } stack = append(stack, points[i]) } return stack } func main() { points := []Point{ {0, 3}, {2, 2}, {1, 1}, {2, 1}, {3, 0}, {0, 0}, {3, 3}, } hull := GrahamScan(points) fmt.Println("凸包点（逆时针）：") for _, p := range hull { fmt.Printf("(%d, %d)\n", p.X, p.Y) } } 代码详细解读（仅解读方法作用）
1. cross 方法
用于判断三点构成的转向关系，是整个算法的几何核心。
2. GrahamScan 方法
该方法完成了：
- 基准点选择
- 极角排序
- 栈扫描与回退
- 最终凸包构建
返回的点集已经按逆时针顺序排列。
3. 栈扫描逻辑
通过不断“回退右转点”，确保最终结果只包含凸包边界点。
项目详细总结
通过本项目，我们完整实现了 Graham Scan 算法，并理解了：
- 几何问题如何转化为代数判断
- 叉积在方向判断中的核心地位
- O(n log n) 算法的工程实现方式
- 栈结构在几何扫描中的巧妙应用
Graham Scan 是：
- 凸包算法的入门首选
- 计算几何的经典代表
- 极具教学价值的算法范例
项目常见问题及解答
Q1：为什么要极角排序？
为了保证扫描是单调逆时针进行，避免回头判断。
Q2：共线点如何处理？
通过距离排序 + 回退逻辑，只保留最外层点。
Q3：时间复杂度是多少？
- 排序：O(n log n)
- 扫描：O(n)
- 总体：O(n log n)
Q4：可以处理浮点坐标吗？
可以，但需要注意精度误差，教学与工程中更推荐整数。
扩展方向与性能优化
- 改写为泛型版本（Go 1.18+）
- 支持浮点坐标与 EPS 判断
- 与 Jarvis March 算法对比
- 用于多边形面积 / 周长计算
- 结合可视化工具展示扫描过程
