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

技術支持 / 技術論壇 / 二次開發 / 【技術分享】【C#】凸包算法
【技術分享】【C#】凸包算法
freeter
帖子
1
精華
0
積分
12
二次開發 技術分享

一、參考鏈接:點擊鏈接

二、實現代碼:

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

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

三、效果圖

860 0 2024-01-05 18:03:42
暫時還沒有回復評論

回復加入討論

回復
請選擇移動至版塊:
確認移動
主站蜘蛛池模板: 免费能看大奶子的黄色1片. | 亚州中文无码aⅤ在线 | 成人午夜免费福利视频 | 草逼逼视频 | 一级免费黄色片 | 欧美成人综合一区二区三区 | 亚洲精品在线第一页 | 日韩激情一区 | 日韩一区二区三区无码免费视频 | 久久不卡视频 | 香蕉噜噜噜噜私人影院 | 久久中文字幕人妻丝袜系列 | 国v1区区免费线观看 | 911亚洲精品777777 | 日韩在线视频免费观看 | 国产精品日韩一区二区免费视频 | 97人妻人人揉人人躁人人 | 国产亚洲欧洲AV综合一区二区三区 | 色婷婷综合久久久久中文字幕小说 | 97国产精品欲 | 懂色av中文一区二区在 | 日本亚洲精品中字幕日产2020 | 黑人外教啪啪中国女留学生 | 最近免费日本视频在线 | 成人精品后入三区丝袜激情一区二区 | 久久毛片视频 | 亚洲高清一区二区三区免费 | caoprom人人 | 国产一区二区福利 | 无码成人精品日本动漫纯H 在线播放真实国产乱子伦 成人av视 | 白丝小舞被调教的奶水直流 | 午夜性色福利一区二区三区视频 | 免费国产片在线观看 | 国产亚洲精品久久久久久久久久 | 一二三四区在线观看视频 | 亚洲狠狠婷婷综合久久蜜桃 | 靠逼国产 | 人妻系列无码专区AV在线 | 激情欧美一区二区免费视频 | 男人女人午夜视频免费 | 国产亚洲欧洲AV综合一区二区三区 |