Go 语言实现 Graham Scan 凸包算法详解与源码

cross = OA.x * OB.y - OA.y * OB.x

含义：

• cross > 0 ：左转（逆时针）
• cross < 0 ：右转（顺时针）
• cross = 0 ：共线

3. 极角排序（Polar Angle Sort）

Graham Scan 的第一步是：

选一个基准点，然后按极角排序所有其他点

排序规则：

1. 极角从小到大（逆时针）
2. 极角相同，距离基准点近的在前

实现思路

Graham Scan 的整体流程可以概括为四个步骤：

步骤一：选择基准点（Pivot）

从所有点中选出：

• Y 最小
• 若 Y 相同，取 X 最小

该点必然是凸包上的点，用作极角计算的参考。

步骤二：按极角排序

将除基准点外的所有点，按照它们与基准点形成的极角排序。

目的：

• 保证我们是逆时针扫描点集

步骤三：扫描并维护栈

维护一个'栈'（slice）：

1. 先压入前两个点
2. 从第三个点开始：
   • 若出现 右转或共线
   • 弹出栈顶
   • 直到形成左转
3. 当前点入栈

步骤四：栈中剩余点即为凸包

扫描结束后，栈中点：

• 按逆时针顺序
• 正好构成凸包边界

代码实现

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 算法，并理解了：

1. 几何问题如何转化为代数判断
2. 叉积在方向判断中的核心地位
3. O(n log n) 算法的工程实现方式
4. 栈结构在几何扫描中的巧妙应用

Graham Scan 是：

• 凸包算法的入门首选
• 计算几何的经典代表
• 极具教学价值的算法范例

常见问题及解答

Q1：为什么要极角排序？

为了保证扫描是单调逆时针进行，避免回头判断。

Q2：共线点如何处理？

通过距离排序 + 回退逻辑，只保留最外层点。

Q3：时间复杂度是多少？

• 排序：O(n log n)
• 扫描：O(n)
• 总体：O(n log n)

Q4：可以处理浮点坐标吗？

可以，但需要注意精度误差，教学与工程中更推荐整数。

扩展方向与性能优化

1. 改写为泛型版本（Go 1.18+）
2. 支持浮点坐标与 EPS 判断
3. 与 Jarvis March 算法对比
4. 用于多边形面积 / 周长计算
5. 结合可视化工具展示扫描过程