C++实现Graham扫描算法求解凸包问题源代码

简介：
本项目提供了一个用C++编写的程序，实现了Graham扫描算法来解决计算几何中的凸包问题。该算法高效地找出包含所有给定点集的最小凸多边形，并附有详细的注释和测试案例以帮助理解和验证算法的有效性。 Graham扫描算法的基本思路是去除那些不是凸包顶点的点。首先找出集合S中具有最小y坐标的点p（如果多个点有相同的y坐标，则选择最左边的那个）。然后根据每个点与p连线相对于x轴正方向的角度对S中的所有其他点进行排序，并将p置于列表首位。接下来，从p开始扫描已排序的S集合。若这些点都在凸包上，那么对于任意三个连续的点p1, p2, 和 p3，应该满足这样的条件：即在向量的方向上看，p3应在左边。如果发现存在不满足此条件的三点序列（例如p1, p2和p3），则中间的那个点(p2)肯定不在凸包上，并应立即从集合中移除。