【技术分享】【C#】凸包算法
![](/static/image/default_head.jpg)
freeter
帖子
1
1
精华
0
0
积分
12
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;
}
三、效果图
登录论坛用户后可查看全部内容
293
0
2024-01-05 18:03:42
请选择移动至版块:
确认移动
回复加入讨论