凸包

计算几何

说明

将点排序后构建上下链；遇到非左转就移除中间点，时间 O(n log n)。

分析

单调链先按 x、y 排序，再依次构建下凸壳和上凸壳。遇到非左转时删除中间点，保证边界始终凸。

图解推演

为看清弹栈，补充点 A=(0,0)、B=(1,1)、C=(2,0)。构建下凸壳时 A→B→C 是右转，B 位于真正下边界上方，因此弹出 B，连接 A→C。上凸壳从相反方向扫描；拼接时去掉重复端点，并明确共线点是否保留。

查看图表代码

适用前提与边界

示例会修改输入切片的顺序，并省略同一直线上的中间边界点；是否保留这些点取决于应用。它没有预先去重：空输入返回空，单个点直接返回；若多个输入点的坐标全部相同，则会返回两个相同端点，调用方应先按坐标去重，使单一唯一点走单点分支。例如 [{0,0},{0,0}] 应先整理为 [{0,0}]。叉积使用 int，坐标范围还须保证差值与乘积不溢出。

示例输入与调用

fmt.Println(Hull([]Point{{0, 0}, {1, 0}, {1, 1}, {0, 1}, {0, 0}}))

运行输出

[{0 0} {1 0} {1 1} {0 1}]

完整 Go 示例

package main

import (
	"fmt"
	"sort"
)

type Point struct{ X, Y int }

func Hull(points []Point) []Point {
	sort.Slice(points, func(i, j int) bool {
		if points[i].X == points[j].X {
			return points[i].Y < points[j].Y
		}
		return points[i].X < points[j].X
	})
	cross := func(a, b, c Point) int { return (b.X-a.X)*(c.Y-a.Y) - (b.Y-a.Y)*(c.X-a.X) }
	build := func(a []Point) []Point {
		h := []Point{}
		for _, p := range a {
			for len(h) >= 2 && cross(h[len(h)-2], h[len(h)-1], p) <= 0 {
				h = h[:len(h)-1]
			}
			h = append(h, p)
		}
		return h
	}
	if len(points) < 2 {
		return points
	}
	lower := build(points)
	for i, j := 0, len(points)-1; i < j; i, j = i+1, j-1 {
		points[i], points[j] = points[j], points[i]
	}
	upper := build(points)
	return append(lower[:len(lower)-1], upper[:len(upper)-1]...)
}

func main() {
	fmt.Println(Hull([]Point{{0, 0}, {1, 0}, {1, 1}, {0, 1}, {0, 0}}))
}