三河建设厅公示网站,免费个人网页制作成品,推广软件app,网页视频怎么下载到本地视频电脑C#实现凸包算法之Jarvis 文章目录 C#实现凸包算法之Jarvis前言示例代码实现思路测试结果结束语 前言
这篇关于凸包算法的文章#xff0c;本文使用C#和Jarvis算法来实现凸包算法。 首先消除两个最基本的问题#xff1a;
什么是凸包呢#xff1f; 凸包是一个包围一组点的凸多…
C#实现凸包算法之Jarvis 文章目录 C#实现凸包算法之Jarvis前言示例代码实现思路测试结果结束语 前言
这篇关于凸包算法的文章本文使用C#和Jarvis算法来实现凸包算法。 首先消除两个最基本的问题
什么是凸包呢 凸包是一个包围一组点的凸多边形。凸多边形是指多边形中的每个内角都小于180度的多边形。凸包算法有什么用呢 凸包算法的作用是找到这个凸多边形并且使用最少的点来绘制出它的轮廓。凸包算法在计算机图形学、计算几何和机器学习等领域中有着广泛的应用。
示例代码
现在来看一下C#中的Jarvis算法是如何实现凸包算法的 /// summary/// 通过Jarvis算法获取围绕所有点的凸多边形的轮廓点br//// /summary/// param namepoints点数组/param/// returns轮廓点数组/returnspublic static PointD[] GetConvexHullByJarvis(PointD[] points){if (points.Length 3){throw new ArgumentException(凸包算法需要至少3个点);}ListPointD pointList new ListPointD(points);// 找到最左边的点PointD leftmostPoint pointList[0];for (int i 1; i pointList.Count; i){if (pointList[i].X leftmostPoint.X){leftmostPoint pointList[i];}}// 使用栈来存储凸包的点StackPointD hull new StackPointD();PointD currentPoint leftmostPoint;do{hull.Push(currentPoint);PointD endpoint pointList[0];for (int i 1; i pointList.Count; i){if (endpoint.Equals(currentPoint) || Cross(currentPoint, endpoint, pointList[i]) 0){endpoint pointList[i];}}currentPoint endpoint;pointList.Remove(currentPoint);} while (!currentPoint.Equals(leftmostPoint));return hull.ToArray();}上面代码中定义了一个名为GetConvexHullByJarvis的静态方法该方法接受一个PointD类型的数组作为输入参数并返回一个PointD类型的数组表示围绕所有点的凸多边形的轮廓点。
补充一下关于示例中使用到的Cross方法和PointD类型的源代码如下 /// summary/// 计算从 a 到 b 再到 c 的叉积/// /summary/// returns叉积值/returnsprivate static double Cross(PointD a, PointD b, PointD c){return (b.X - a.X) * (c.Y - a.Y) - (b.Y - a.Y) * (c.X - a.X);}public struct PointD {public PointD(double x, double y) {X x;Y y;}public double X { get; set; }public double Y { get; set; }public override bool Equals(object obj){if (obj null || GetType() ! obj.GetType()){return false;}PointD other (PointD)obj;return X.Equals(other.X) Y.Equals(other.Y);}}实现思路
找到最左边的点将它放入凸包中找到在当前点的右侧且离当前点最远的点将它放入凸包中重复这个过程直到回到最左边的点形成一个闭合的凸多边形。
这就是 Jarvis 算法的基本思路。 需要注意的是当点集中存在大量共线的点时Jarvis 算法的时间复杂度可能会退化到 O(n^2) 级别因为需要不断地扫描点集中的点来找到下一个点。此外当点集中存在大量重复的点时Jarvis 算法可能会陷入死循环因此需要对点集进行去重操作。 测试结果
用于测试的数据点 static PointD[] points new PointD[]{ new PointD(0, 0),new PointD(0, 10),new PointD(10, 10),new PointD(10, 0),new PointD(1, 0),new PointD(4, 3),new PointD(5, 2),new PointD(6, 5),new PointD(4, 9),new PointD(4, 2),new PointD(5, 1),new PointD(6, 5),new PointD(1, 3),new PointD(7, 2),new PointD(8, 2),new PointD(6, 7),new PointD(8, 5),new PointD(9, 3),new PointD(7, 8),new PointD(8, 9),};测试代码如下 [TestMethod]public void GetConvexHullByJarvis(){Console.WriteLine(Jarvis 算法);PrintPoints(ConvexHull.GetConvexHullByJarvis(points));}private void PrintPoints(PointD[] points){Console.WriteLine(points.Select(p $ ({p.X}, {p.Y})).Join(\r\n));}执行结果如下 结束语
通过本章的代码可以轻松实现Jarvis算法并找到一组点最外侧的凸多边形。如果您觉得本文对您有所帮助请不要吝啬您的点赞和评论提供宝贵的反馈和建议让更多的读者受益。
