# Basic Convex Hull in C#

Transliterated from java found here:

class ConvexHull { public static double cross(Point O, Point A, Point B) { return (A.X - O.X) * (B.Y - O.Y) - (A.Y - O.Y) * (B.X - O.X); } 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) => a.X == b.X ? a.Y.CompareTo(b.Y) : a.X.CompareTo(b.X)); // 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(); } }