分治法求凸包
本帖最后由 MyNameIsLiLei 于 2020-10-21 16:49 编辑/// <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;
//横坐标最大的点
Point3d end = pts;
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;
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 * vector2 - vector1 * vector2;
}
我想这个速度应该不是很快，我的思路：将离散点集先按X为主、Y为辅从小到大排序，然后分别判断左右两边各点Y值是否大于前一个点（最初是左右两个点）的Y值，只保留大的，两边比较完后就形成一个小的包围所有点多边形（非凸），这个多边形的顶点就很少了，这一过程只需要比较运算。再根据凸包性质比较多边形中各点与前一线段的位置关系优化一下，凸包完成。 比MelkMan法稍微快一点{:1_1:} 本帖最后由 MyNameIsLiLei 于 2020-10-26 10:55 编辑
mkhsj928 发表于 2020-10-24 16:20
比MelkMan法稍微快一点
嗯，这个只是利用归并排序的思路，简单的一个实现方式。
页:
[1]