经典算法——凸包算法

凸包算法（Convex Hull）

一、概念与问题描述

凸包是指在平面上给定一组点，找到包含这些点的最小面积或最小周长的凸多边形。这个多边形没有任何内凹部分，即从一个多边形内的任意一点画一条线到多边形边界上的任何一点，这条线段都不可能穿过多边形的边界。

二、主要算法

1. Graham扫描法：

o 基于极角排序，首先找到最左下点作为起始点。

o 按照逆时针方向对所有点进行极角排序，并维护一个大小为2的栈来记录当前凸包上的点。

o 遍历排序后的点，根据栈顶两点和当前点构成的向量判断是否应该将当前点加入凸包。

2. Jarvis步进法（又称 gift wrapping 算法）：

o 从最左或者最右的点开始，按顺时针或逆时针方向依次选择使包络线角度变化最大的点，直到回到起点形成闭合链。

3. Chan算法：

o 对于大规模数据集，Chan算法提供了更高效的在线计算方法。

C++ 示例代码片段（使用 Graham 扫描法）：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

struct Point {
	double x, y;
	Point(double x = 0, double y = 0) : x(x), y(y) {}
};
// 判断三点是否逆时针排列
bool ccw(const Point& a, const Point& b, const Point& c) {
	double crossProduct = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
	return crossProduct > 0;
}
// 使用Graham扫描法求凸包
std::vector<Point> convexHull(std::vector<Point>& points) {
	// 第一步：去除重复点并找出最左下点
	auto minPoint = std::min_element(points.begin(), points.end(),
		[](const Point& a, const Point& b) -> bool { return a.y < b.y || (a.y == b.y && a.x < b.x); });
	std::rotate(points.begin(), minPoint, points.end());
	// 第二步：按照极角排序
	std::sort(points.begin() + 1, points.end(), [&](const Point& a, const Point& b) {
		double dx1 = points[0].x - a.x, dy1 = points[0].y - a.y;
		double dx2 = points[0].x - b.x, dy2 = points[0].y - b.y;
		if (dy1 * dx2 > dy2 * dx1) return true; // 逆时针排序
		return false;
		});

	// 第三步：执行Graham扫描
	std::vector<Point> hull;
	hull.push_back(points[0]);
	hull.push_back(points[1]);
	for (size_t i = 2; i < points.size(); ++i) {
		while (hull.size() >= 2 && !ccw(hull[hull.size() - 2], hull.back(), points[i])) {
			hull.pop_back();
		}
		hull.push_back(points[i]);
	}
	return hull;
}
int main() {
	std::vector<Point> points = { {1, 1}, {2, 2}, {2, 1}, {1, 2}, {3, 3}, {3, 2} };
	std::vector<Point> hull = convexHull(points);
	// 输出结果
	for (const auto& p : hull) {
		std::cout << "(" << p.x << ", " << p.y << ") ";
	}
	std::cout << "\n";
	return 0;
}

上述代码演示了如何使用C++实现基于Graham扫描法的凸包算法。注意，实际应用中还需要处理特殊情况，例如输入点数少于3个的情况。此外，上述代码没有包含检查输入合法性及优化步骤。