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

Question

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

任何帮助将不胜感激，

此致，

丹尼尔

Answer 1

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

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

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

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

这是极简代码（它在 O( n ³) 中运行，其中n是点数）：

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

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

Answer 2

我知道 AForge 没有凹壳。如果你想计算它，你需要使用 EmguCV。