볼록 선체 라이브러리

Question

저는 C#에 익숙하지 않으며 볼록 선체를 계산하는 데 어려움을 겪고 있습니다. C#에는이를위한 일종의 수학 라이브러리가 있습니까? 그렇지 않다면 나는 내 자신을 구현해야 할 것 같아요.

Answer 1

MIConvexHull-https://designengrlab.github.io/MIConvexHull/ - C#의 고성능 볼록 선체 구현으로 고차원 컨벡션 헐 (hull)도 지원합니다. LGPL 라이센스.

Answer 2

여기는 Monotone Chain 알고리즘 인 앤드류 알고리즘 (Andrew 's Algorithm)을 사용하여 작성한 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; 
} 

존재하는 것으로 간주되는 일부 사항에 의존합니다. 자세한 내용은 내 blog post을 참조하십시오.

Answer 3

다음은 Qwertie의 대답에 사용 된 동일한 Java 소스의 음역이지만 이중 필드가있는 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(); 
    } 
} 

Answer 4

제공된 모든 코드로 많은 볼록 알고리즘/구현을 비교했습니다. 모든 것은 CodeProject 기사에 포함됩니다.

알고리즘 비교 :

그레이엄

찬 스캔

• 모노톤 체인
• MiConvexHull (들로네 삼각 측량 및 보로 노이 그물코)
• Ouellet (내)

문서 :

• 2017년 10월 13일 - 5 월 알고리즘/구현과 테스트 벤치 - Fast and improved 2D Convex Hull algorithm and its implementation in O(n log h)
• 2014년 5월 20일 내 자신의 알고리즘을 설명합니다 : A Convex Hull Algorithm and its implementation in O(n log h)