精品免费久久久_亚洲VA中文字幕无码毛片_成人黄色片在线观看_变态SM天堂无码专区_亚洲视频在线观看一区二区三区_伊人色综合久久天天五月婷

一、參考鏈接：點擊鏈接

二、實現代碼：

注：傳進去的點集坐標是要相對于所在平面坐標，不符合條件需要轉換。

        /// <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;
        }

三、效果圖