Thư viện thân tàu lồi

Question

Tôi mới sử dụng C# và đang gặp khó khăn trong việc tính toán vỏ lồi. Có C# có một số loại của một thư viện toán học cho điều này? Nếu không, thì tôi đoán tôi sẽ phải tự mình thực hiện.

Answer 1

MIConvexHull - https://designengrlab.github.io/MIConvexHull/ - là một hiệu suất cao lồi thực hiện thân tàu trong C#, hỗ trợ vỏ lồi cao hơn chiều quá. Giấy phép LGPL.

Answer 2

Đây là thuật toán lồi 2D lồi mà tôi đã viết bằng thuật toán Monotone Chain, thuật toán của Andrew.b.a.

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

Nó dựa vào một số điều được cho là tồn tại, xem chi tiết blog post của tôi.

Answer 3

Dưới đây là một chuyển ngữ thành C# của cùng một nguồn Java được sử dụng trong câu trả lời của Qwertie nhưng không phụ thuộc vào các lớp không chuẩn ngoài lớp Point với các trường kép.

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

Answer 4

Tôi đã so sánh nhiều thuật toán/triển khai của Convex Hull với tất cả mã được cung cấp. Mọi thứ được bao gồm trong bài viết CodeProject.

Thuật toán so sánh:

• chuỗi đơn điệu
• MiConvexHull (Delaunay triangulations và Voronoi meshes)
• Graham quét
• Chan
• Ouellet (mỏ)

bài viết:

• 2017/10/13 - băng ghế dự bị thử nghiệm với thuật toán tháng/triển khai: Fast and improved 2D Convex Hull algorithm and its implementation in O(n log h)
• 2014/05/20 - Giải thích thuật toán của riêng tôi: A Convex Hull Algorithm and its implementation in O(n log h)