凸壳船库
我是C＃的新手，并且很难计算凸包。 C＃是否有某种数学库？ 如果没有，那么我想我只需要实现自己的。
MIConvexHull – https://designengrlab.github.io/MIConvexHull/–是C＃中的高性能凸包实现，也支持更高维的凸包。 LGPL许可证。
这是我使用Monotone Chain算法编写的2D凸包算法，也就是Andrew的算法。
public static IListSource ComputeConvexHull(List points, bool sortInPlace = false) { if (!sortInPlace) points = new List (points); points.Sort((a, b) => aX == bX ? aYCompareTo(bY) : aXCompareTo(bX)); // Importantly, DList provides O(1) insertion at beginning and end DList hull = new DList (); int L = 0, U = 0; // size of lower and upper hulls // Builds a hull such that the output polygon starts at the leftmost point. for (int i = points.Count - 1; i >= 0 ; i--) { Point p = points[i], p1; // build lower hull (at end of output list) while (L >= 2 && (p1 = hull.Last).Sub(hull[hull.Count-2]).Cross(p.Sub(p1)) >= 0) { hull.RemoveAt(hull.Count-1); L--; } hull.PushLast(p); L++; // build upper hull (at beginning of output list) while (U >= 2 && (p1 = hull.First).Sub(hull[1]).Cross(p.Sub(p1)) <= 0) { hull.RemoveAt(0); U--; } if (U != 0) // when U=0, share the point added above hull.PushFirst(p); U++; Debug.Assert(U + L == hull.Count + 1); } hull.RemoveAt(hull.Count - 1); return hull; }
它依赖于假设存在的一些东西，请参阅我的博客文章了解详细信息。
我将许多Convex Hull算法/实现与所提供的所有代码进行了比较。 一切都包含在CodeProject文章中。
算法比较：
- 单调链
- MiConvexHull（Delaunay三角剖分和Voronoi网格）
- 格雷厄姆扫描
- 陈
- Ouellet（我的）
文章：
- 2017-10-13 – 具有may算法/实现的测试平台： 快速和改进的2D Convex Hull算法及其在O（n log h）中的实现
- 2014-05-20 – 解释我自己的算法： 一个凸壳算法及其在O（n log h）中的实现
下面是对Qwertie的答案中使用的相同Java源代码的C＃的音译，但没有依赖于具有双字段的Point类之外的非标准类。
class ConvexHull { public static double cross(Point O, Point A, Point B) { return (AX - OX) * (BY - OY) - (AY - OY) * (BX - OX); } public static List GetConvexHull(List points) { if (points == null) return null; if (points.Count() <= 1) return points; int n = points.Count(), k = 0; List H = new List (new Point[2 * n]); points.Sort((a, b) => aX == bX ? aYCompareTo(bY) : aXCompareTo(bX)); // Build lower hull for (int i = 0; i < n; ++i) { while (k >= 2 && cross(H[k - 2], H[k - 1], points[i]) <= 0) k--; H[k++] = points[i]; } // Build upper hull for (int i = n - 2, t = k + 1; i >= 0; i--) { while (k >= t && cross(H[k - 2], H[k - 1], points[i]) <= 0) k--; H[k++] = points[i]; } return H.Take(k - 1).ToList(); } }