C#中的Alpha形状（凹壳）算法

Question

我需要凹算法来从一组点中勾勒出形状，AForge.NET 中是否有我可以使用的实现，我在某处读到 AForge.NET 有该算法的实现，但我在文档中找不到它.

任何帮助将不胜感激，

此致，

丹尼尔

Answer 1

我也在寻找一个简单的 .NET 实现来创建一个 alpha 形状，但找不到。所以我自己做了。苏黎世联邦理工学院的 Kaspar Fischer 在本文档中提供了重要的见解。

这个想法只是简单地用半径为 alpha 的圆形勺子吃掉有限点集的周围空间，而实际上没有击中这些点。这是 Kaspar 论文中的一张图片：

现在，每个在其边界上恰好包含两个点但内部没有点的圆都被称为alpha 暴露(AEC)，正是这些 AEC 为您提供了最终的 alpha 形状——只需将定义 AEC 的两个点替换为边.

注意：如果您的 alpha 形状看起来太像凸包，请将 alpha 变小。另一方面，如果您的 alpha 形状碎片化或其中有太多洞，请使 alpha 更大。

下面是极简代码（它运行在O（ñ ³），其中ñ IST点数）：

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

而且，作为概念证明，以下是实际应用程序中使用的代码的输出：