Bet韦德(中国)VIP官方认证·百度百科

一、参考链接：点击链接

二、实现代码：

注：传进去的点集坐标是要相对于所在平面坐标，不符合条件需要转换。

        /// <summary>
        /// Graham扫描法主函数
        /// </summary>
        /// <param name="points"></param>
        /// <returns></returns>
        internal static List<Point3> GrahamScan(List<Point3> points)
        {
            // 如果点的个数小于等于2，直接返回所有点
            if (points.Count <= 2)
                return points;

            List<Point3> convexHull = new List<Point3>();

            // 1. 找到包含所有点中最下方的点，并将其放在列表的第一个位置
            Point3 lowestPoint = FindLowestPoint(points);
            points.Remove(lowestPoint);
            convexHull.Add(lowestPoint);

            // 2. 根据极角对其它点进行排序
            points.Sort((p1, p2) =>
            {
                double angle1 = GetPolarAngle(lowestPoint, p1);
                double angle2 = GetPolarAngle(lowestPoint, p2);
                return angle1.CompareTo(angle2);
            });

            // 3. 构建凸包
            convexHull.Add(points[0]);
            for (int i = 1; i < points.Count; i++)
            {
                while (convexHull.Count >= 2 && !IsCounterClockwise(convexHull[convexHull.Count - 2], convexHull[convexHull.Count - 1], points[i]))
                {

                    convexHull.RemoveAt(convexHull.Count - 1);
                }
                convexHull.Add(points[i]);
            }
            return convexHull;
        }
        /// <summary>
        /// 使用极角排序，辅助函数：计算极角
        /// </summary>
        /// <param name="p1"></param>
        /// <param name="p2"></param>
        /// <returns></returns>
        protected static  double GetPolarAngle(Point3 p1, Point3 p2)
        {
            double deltaX = p2.X - p1.X;
            double deltaY = p2.Y - p1.Y;
            return Math.Atan2(deltaY, deltaX);
        }

        /// <summary>
        /// 使用极角排序，辅助函数：判断点p3是否在p1和p2的逆时针方向
        /// </summary>
        /// <param name="p1"></param>
        /// <param name="p2"></param>
        /// <param name="p3"></param>
        /// <returns></returns>
        protected static bool IsCounterClockwise(Point3 p1, Point3 p2, Point3 p3)
        {
            double crossProduct = (p2.X - p1.X) * (p3.Y - p1.Y) - (p2.Y - p1.Y) * (p3.X - p1.X);
            return crossProduct > 0;
        }

        /// <summary>
        /// 寻找包含所有点中最下方的点
        /// </summary>
        /// <param name="points"></param>
        /// <returns></returns>
        protected static Point3 FindLowestPoint(List<Point3> points)
        {
            Point3 lowest = points[0];
            foreach (var point in points)
            {
                if (point.Y < lowest.Y || (point.Y == lowest.Y && point.X < lowest.X))
                    lowest = point;
            }
            return lowest;
        }

三、效果图