什么是凸包算法？详述凸包算法的原理？用C语言实现凸包算法。内附完整代码。

大家好，我是贤弟！

一、什么是凸包算法？

凸包算法是一种计算在平面上给定点集的最小凸多边形的算法。

凸多边形是指对于任意两个顶点，这两个顶点之间的线段不会穿过凸多边形的内部。

二、常用的凸包算法

其中比较常用的凸包算法有 Graham 扫描法和 Andrew 算法。

下面以 Graham 扫描法为例进行介绍：

1、找到点集中纵坐标最小的点，并按照极角从小到大排序，排序规则为：若极角相同，则距离近的点排在前面；

2、选取排序后的第一个点和第二个点，以这两个点为起始点构建凸包；

3、依次选取下一个点，如果该点在当前凸包的外侧，则将该点加入凸包，否则将该点弹出凸包。具体判断方式为，假设已经有凸包上的两个相邻点 A 和 B，和需要判断的点 C，计算向量 AB 和 AC 的叉积，若结果为正，则 C 在 AB 的逆时针方向，即在凸包外侧，否则在凸包内侧；

4、重复步骤三，直至所有点都被处理，并得到凸包。

三、代码示例

下面是使用 C 语言实现 Graham 扫描法的代码示例：