logo标签列表

如何在C#中计算凸包

c#convex-hull
10

如何从点集计算凸包？

我正在寻找一个C#实现的凸包算法。

1
是的，我看到了。我的问题是C#是否有现成的内置库... - Owen
可能可以重新打开，因为有带代码的答案（相同算法），以及对库/博客的引用。编辑后删除了“给我库”的部分。 - Alexei Levenkov
4个回答
13

以下是将与Qwertie答案中相同的Java源代码转换为C#的音译，但不依赖于除具有双字段的Point类之外的非标准类。

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();
    }
}
12
1
许可证似乎是MIT而不是LGPL。 - tombola
1
许可证似乎是MIT而不是LGPL。 - undefined
4

这是我使用单调链算法(也称为Andrew's算法)编写的2D凸包算法。

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

它依赖于一些假设存在的东西，请参阅我的博客文章获取详细信息。

3
@ephraim，非常感谢您向我报告。我目前正在查看那个案例！ - Eric Ouellet
@ephraim，你在哪篇文章中发现了这个错误？我用最新文章的代码无法重现它。你有什么提示可以让我自己看到这个错误吗？使用所有Ouellet算法进行100万次测试，每个象限应该偶尔会得到1个点，但没有错误/异常？ - Eric Ouellet
@ephraim，发现了一个Bug！非常感谢！Bug只存在于第一篇文章中。带有更正的文章很快就会发布（将在15分钟内推出，并在CodeProject批准后即可使用~可能是今天）。 - Eric Ouellet
谢谢！真是一个很棒的库（已删除错误报告...尤其是在修复后...+它非常微小） - ephraim
欢迎。但我非常感谢知道这个 bug。非常感谢你！如果有任何问题，请随时报告更多。 - Eric Ouellet
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接