Alpha shape (concave hull) algorithm in C#

Question

I'm in need of concave algorithm to outline shape from set of points, is there implementation in AForge.NET that I could use, I have read somewhere that AForge.NET has implementation of that algorithm but I can't find it in documentation.

Any help would be greatly appreciated,

Best regards,

Daniel

Answer 1

I was also looking for a simple .NET implementation creating an alpha shape but couldn't find one. So I did my own. The crucial insights were provided by ETH Zurich‘s Kaspar Fischer in this document.

The idea is simply eating up the surrounding space of a finite point set with a circular spoon of radius alpha without actually hitting the points. Here's an image from Kaspar's paper:

Now, every circle that contains exactly two points on its boundary but none inside is said to be alpha-exposed (AEC), and it's these AEC that give you the eventual alpha shape--just replace the two points defining an AEC by an edge.

Note: If your alpha shape looks too much like a convex hull, make alpha smaller. If, on the other hand, your alpha shape is fragmented or has too many holes in it, make alpha larger.

Here's the minimalist code (it runs in O(n³), where n ist the number of points):

public class Edge
{
    public PointF A { get; set; }
    public PointF B { get; set; }
}

public class AlphaShape
{
    public List<Edge> BorderEdges { get; private set; }

    public AlphaShape(List<PointF> points, float alpha)
    {
        // 0. error checking, init
        if (points == null || points.Count < 2) { throw new ArgumentException("AlphaShape needs at least 2 points"); }
        BorderEdges = new List<Edge>();           
        var alpha_2 = alpha * alpha;

        // 1. run through all pairs of points
        for (int i = 0; i < points.Count - 1; i++)
        {
            for (int j = i + 1; j < points.Count; j++)
            {
                if (points[i] == points[j]) { throw new ArgumentException("AlphaShape needs pairwise distinct points"); } // alternatively, continue
                var dist = Dist(points[i], points[j]);                    
                if (dist > 2 * alpha) { continue; } // circle fits between points ==> p_i, p_j can't be alpha-exposed                    

                float x1 = points[i].X, x2 = points[j].X, y1 = points[i].Y, y2 = points[j].Y; // for clarity & brevity

                var mid = new PointF((x1 + x2) / 2, (y1 + y2) / 2);

                // find two circles that contain p_i and p_j; note that center1 == center2 if dist == 2*alpha
                var center1 = new PointF(
                    mid.X + (float)Math.Sqrt(alpha_2 - (dist / 2) * (dist / 2)) * (y1 - y2) / dist,
                    mid.Y + (float)Math.Sqrt(alpha_2 - (dist / 2) * (dist / 2)) * (x2 - x1) / dist
                    );

                var center2 = new PointF(
                    mid.X - (float)Math.Sqrt(alpha_2 - (dist / 2) * (dist / 2)) * (y1 - y2) / dist,
                    mid.Y - (float)Math.Sqrt(alpha_2 - (dist / 2) * (dist / 2)) * (x2 - x1) / dist
                    );

                // check if one of the circles is alpha-exposed, i.e. no other point lies in it
                bool c1_empty = true, c2_empty = true;
                for (int k = 0; k < points.Count && (c1_empty || c2_empty); k++)
                {
                    if (points[k] == points[i] || points[k] == points[j]) { continue; }

                    if ((center1.X - points[k].X) * (center1.X - points[k].X) + (center1.Y - points[k].Y) * (center1.Y - points[k].Y) < alpha_2)
                    {
                        c1_empty = false;
                    }

                    if ((center2.X - points[k].X) * (center2.X - points[k].X) + (center2.Y - points[k].Y) * (center2.Y - points[k].Y) < alpha_2)
                    {
                        c2_empty = false;
                    }                                                
                }

                if (c1_empty || c2_empty)
                {                       
                    // yup!
                    BorderEdges.Add(new Edge() { A = points[i], B = points[j] });
                }
            }
        }
    }

    // Euclidian distance between A and B
    public static float Dist(PointF A, PointF B)
    {
        return (float)Math.Sqrt((A.X - B.X) * (A.X - B.X) + (A.Y - B.Y) * (A.Y - B.Y));
    }      
}

And, as a proof of concept, here's the output of the code used in an actual app:

Answer 2

i know that AForge DONT have the Concave Hull. You need to use EmguCV if you want compute it.