How to compute Convex Hull in C#

Question

How to compute the convex hull starting from collection of points?

I am looking for an implementation of Convex hull algorithm in C#

Brashear

yes, I've seen that. My question was if C# has an existing built in library for it... – Brashear

May be ok to re-open as there is answers with code (same algo), as well as references to libraries/blogs. Edited to remove "give me library" part. – Mixer

Answer 1

MIConvexHull - https://designengrlab.github.io/MIConvexHull/ - is a high-performance convex hull implementation in C#, supporting higher-dimensional convex hulls too. MIT license.

Mariande

The license appears to be MIT rather than LGPL. – Careworn

Answer 2

Below is a transliteration to C# of the same Java source used in Qwertie's answer but without a dependency on non-standard classes beyond a Point class with double fields.

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();
    }
}

Arcuate

Answer 3

Here's a 2D convex hull algorithm that I wrote using the Monotone Chain algorithm, a.k.a. Andrew's Algorithm.

public static IListSource<Point> ComputeConvexHull(List<Point> points, bool sortInPlace = false)
{
    if (!sortInPlace)
        points = new List<Point>(points);
    points.Sort((a, b) => 
        a.X == b.X ? a.Y.CompareTo(b.Y) : a.X.CompareTo(b.X));

    // 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;
}

It relies on some things that are assumed to exist, see my blog post for details.

Beaumont

Answer 4

I compared many Convex Hull algorithm/implementations with all the code provided. Everything is include in a CodeProject article.

Algorithm compared:

• Monotone chain
• MiConvexHull (Delaunay triangulations and Voronoi meshes)
• Graham scan
• Chan
• Ouellet (mine)

Articles:

• 2017-10-13 - Test bench with my algorithm/implementations: Fast and improved 2D Convex Hull algorithm and its implementation in O(n log h)
• 2014-05-20 - Explain my own algorithm: A Convex Hull Algorithm and its implementation in O(n log h)

Machree

@ephraim, Thanks a lots for reporting it to me. I'm currently looking at that case! – Machree

@ephraim, Where do you had the bug, in which article? I can't reproduce it with code from my latest article? Do you have a hint on how I can see the bug myself? 1 000 000 tests with 4 points (which should results in 1 point by quadrant once in a while) with all Ouellet aglorithms and no error/exception? – Machree

@ephraim, Bug found! Thanks a lots! It was only in first article. the article with the correction should be available very soon (will be in the pipeline in 15 minutes and will be available when approved by CodeProject ~ probably today) – Machree

Thanks! Really great library (Deleted the bug report.. - especially after fixing it...+ it was very minor) – Zerk

You are welcome. But I really appreciated to know the bug. Thanks you very much! Don't hesitate to report more if any. – Machree