Convex Hull Library

Question

I am new to C # and have difficulty calculating a convex hull. Does C # have any kind of math library for this? If not, then I think I just need to implement my own.

Answer 1

MIConvexHull - https://designengrlab.imtqy.com/MIConvexHull/ is a high-performance convex hull in C # that supports higher speed, dimensional convex hulls. License LGPL.

Answer 2

Here is a 2D convex hull algorithm that I wrote using the Monotone Chain algorithm, Andrew.Aa Andrew algorithm.

public static IListSource<Point> ComputeConvexHull(List<Point> points, bool sortInPlace = false) { if (!sortInPlace) points = new List<Point>(points); points.Sort((a, b) => aX == bX ? aYCompareTo(bY) : aXCompareTo(bX)); // Importantly, DList provides O(1) insertion at beginning and end DList<Point> hull = new DList<Point>(); 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; } 

He relies on some of the things that are supposed to exist; see the blog post for details.

Answer 3

The following is a C # transliteration of the same Java source as in Qwertie's answer, but without dependency on non-standard classes outside of the Point class with double fields.

 class ConvexHull { public static double cross(Point O, Point A, Point B) { return (AX - OX) * (BY - OY) - (AY - OY) * (BX - OX); } public static List<Point> GetConvexHull(List<Point> points) { if (points == null) return null; if (points.Count() <= 1) return points; int n = points.Count(), k = 0; List<Point> H = new List<Point>(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(); } } 

Answer 4

I have compared many Convex Hull algorithms / implementations with all the code provided. Everything is included in the CodeProject article.

Algorithm Comparison:

• Monotone chain
• MiConvexHull (Delaunay triangulation and Voronoi mesh)
• Graham Scan
• Chan
• Ouellet (mine)

Articles:

• 2017-10-13 - Test bench with algorithm / implementations: Fast and improved 2D-convex Hall algorithm and its implementation in O (n log h)
• 2014-05-20 - Explain your own algorithm: The convex hull algorithm and its implementation in O (n log h)