分治法求凸包

MyNameIsLiLei

        /// <summary>
        /// 求凸包(分治法)
        /// </summary>
        /// <param name="pts">点集合</param>
        public static List<Point3d> Get_Convex_Hull(List<Point3d> pts)
        {
            /* 计算过程:
             * 1.在一个点集合中  首先取出最左边和最右边的点(x最小和最大的点  一定是凸包上的点)
             * 2.以1中的两点为分界线  将集合分为上凸包点集合和下凸包点集合两部分
             *   利用叉乘的方向性,以最左边的点为起点,最右边的点为终点构造虚拟线段,循环整个点集合,计算当前点与虚拟线段的叉乘
             *   叉乘结果大于0的一定在线段的上方,叉乘结果小于0的在线段的下方
             *   按以上计算方法将原点集合分成两部分(上凸包,下凸包)
             * 3.先计算上凸包集合中的点(下凸包类似)
             *   3.1.求出上凸包集合中当前点距离2中虚拟线段最远的点(求叉乘结果最大的那个即是),
             *   3.2.用3.1中的点与虚拟线段的起点构造新的虚拟线段,求出距离最远的点
             *   3.3.用3.1中的点与虚拟线段的终点构造新的虚拟线段,求出距离最远的点
             *   3.4.迭代循环.
             */
            if (pts.Count < 3)
                return pts;
            double max = -10000000000000000;
            double min = 10000000000000000;
            int minIndex = -1;
            int maxIndex = -1;
            /*求出横坐标最小和最大的点*/
            for (int i = 0; i < pts.Count; i++)
            {
                if (pts.X < min)
                {
                    min = pts.X;
                    minIndex = i;
                }
                if (pts.X > max)
                {
                    max = pts.X;
                    maxIndex = i;
                }
            }
            if (minIndex == maxIndex)
                return null;
            //上凸包顶点集合
            List<Point3d> uppts = new List<Point3d>();
            //下凸包顶点集合
            List<Point3d> downpts = new List<Point3d>();
            //横坐标最小的点
            Point3d start = pts[minIndex];
            //横坐标最大的点
            Point3d end = pts[maxIndex];
            double length = 0;
            //将原顶点集合分配到上凸包集合和下凸包集合
            for (int i = 0; i < pts.Count; i++)
            {
                length = CrossProduct(start, end, pts);
                if (length > 0)
                {
                    uppts.Add(pts);
                }
                else if (length < 0)
                {
                    downpts.Add(pts);
                }
            }
            //计算上凸包
            List<Point3d> result1 = new List<Point3d>();
            Get_Convex_Hull(start, end, uppts, result1);
            //计算下凸包
            List<Point3d> result2 = new List<Point3d>();
            Get_Convex_Hull(end, start, downpts, result2);
            /*将上下凸包计算得到的结果按排序后拼接到一起组成最终结果*/
            result1 = result1.OrderBy(pre => pre.X).ToList();
            result1.Insert(0, start);
            result1.Add(end);
            result2 = result2.OrderByDescending(pre => pre.X).ToList();
            result1.AddRange(result2);
            return result1;
        }


        /// <summary>
        /// 计算过程
        /// </summary>
        /// <param name="start">虚拟线段的起点</param>
        /// <param name="end">虚拟线段的终点</param>
        /// <param name="pts">源数据顶点集合</param>
        /// <param name="result">存储最终的结果</param>
        private static void Get_Convex_Hull(Point3d start, Point3d end, List<Point3d> pts, List<Point3d> result)
        {
            double max = 0;
            int index = -1;
            double length = 0;
            for (int i = 0; i < pts.Count; i++)
            {
                length = CrossProduct(pts, start, end);
                if (length > max)
                {
                    index = i;
                    max = length;
                }
            }
            if (index > -1)
            {
                Point3d center = pts[index];
                pts.RemoveAt(index);
                result.Add(center);
                List<Point3d> leftpts = new List<Point3d>();
                List<Point3d> rightpts = new List<Point3d>();
                length = 0;
                for (int i = 0; i < pts.Count; i++)
                {
                    length = CrossProduct(start, center, pts);
                    if (length > 0)
                    {
                        leftpts.Add(pts);
                    }
                    else
                    {
                        length = CrossProduct(center, end, pts);
                        if (length > 0)
                        {
                            rightpts.Add(pts);
                        }
                    }
                }
                /*迭代*/
                //计算左边部分
                Get_Convex_Hull(start, center, leftpts, result);
                //计算右边部分
                Get_Convex_Hull(center, end, rightpts, result);
            }
        }

        public static double CrossProduct(Point3d p1, Point3d p2, Point3d p3)
        {
            double[] v1 = new double[] { p1.X - p2.X, p1.Y - p2.Y };
            double[] v2 = new double[] { p1.X - p3.X, p1.Y - p3.Y };
            return CrossProduct(v1, v2);
        }

        public static double CrossProduct(double[] vector1, double[] vector2)
        {
            return vector1[0] * vector2[1] - vector1[1] * vector2[0];
        }

mkhsj928

我想这个速度应该不是很快，我的思路：将离散点集先按X为主、Y为辅从小到大排序，然后分别判断左右两边各点Y值是否大于前一个点（最初是左右两个点）的Y值，只保留大的，两边比较完后就形成一个小的包围所有点多边形（非凸），这个多边形的顶点就很少了，这一过程只需要比较运算。再根据凸包性质比较多边形中各点与前一线段的位置关系优化一下，凸包完成。

mkhsj928

比MelkMan法稍微快一点

MyNameIsLiLei

mkhsj928 发表于 2020-10-24 16:20
比MelkMan法稍微快一点

嗯，这个只是利用归并排序的思路，简单的一个实现方式。