ConvexHull Algorithm (블록껍질 알고리즘)

ConvexHull

정의

임의의 점들의 집합에서 해당 집합을 감싸는 가장 큰 외곽선을 찾는다.

구현

1) 여러 개의 점을 기준에 따라 정렬한다.

var sorted = Sort(items, selector);

아래는 점들을 정렬하기 위한 함수이다. 가장 좌하단에 있는 점을 찾고, 그 점과 이루는 각에 따라 오름차순으로 정렬한다. 각도가 같을 경우에는 가까운 순으로 정렬한다.

private static List<T> Sort<T>(IEnumerable<T> items, Func<T, Point> selector)
{
    // 좌하단 기준점 수집
    var first = items
        .MinItems(item => selector(item).Y)
        .MinItem(item => selector(item).X);

    return items
        .OrderBy(i => GetDegree(selector(i) - selector(first)))
        .ThenBy(i => GetDistance(selector(i), selector(first)))
        .ToList();
}

2) 여러 점의 개수만큼의 크기의 Stack을 준비한다.

var stack = new Stack<T>(sorted.Count);

3) 정렬된 목록의 첫번 째, 두번 째 항목을 Stack에 집어넣는다.

stack.Push(sorted[0]);
stack.Push(sorted[1]);

4) 첫째 점 (pt1), 둘째 점 (pt2), 셋째 점(pt3)이 이루는 각을 계산한다.

아래는 각을 계산하는 방법이다. 세 점을 순서대로 연결했을 때, pt2에서의 각을 계산하고 해당 각이 CCW인지 CW인지 확인하는 방법이다. 이때 ConvexHull 탐색에서는 반시계 방향으로 탐색을 진행하기 때문에 이루는 각이 CCW이어야 한다.

private static bool IsCCW(Point pt1, Point pt2, Point pt3)
{
    return (pt1.X * pt2.Y + pt2.X * pt3.Y + pt3.X * pt1.Y)
        - (pt2.X * pt1.Y + pt3.X * pt2.Y + pt1.X * pt3.Y) > 0;
}

5) Stack에서 3개의 점을 pop하여 좌하단의 점에 도달할 때까지 3) 단계를 반복한다.

 

int idx = 2;
while (idx < sorted.Count)
{
    var item1 = stack.Pop();
    var item2 = stack.Pop();
    var nextItem = sorted[idx];

    // * 정상 단계
    // pt1, pt2와 이루는 각도가 좌측 방향인 경우 
    // pt1, pt2, next를 모두 stack에 넣고 다음 단계 진행
    if (IsCCW(item2, item1, nextItem, selector))
    {
        stack.Push(item2);
        stack.Push(item1);
        stack.Push(nextItem);
        idx++;
    }
    // * 비정상 단계
    // 좌측 방향이 아니며, Stack이 비어있지 않을 경우
    // pt1로부터 다음 pt2에 대한 단계 진행
    else if (stack.Any())
    {
        stack.Push(item2);
    }
    // * 특별 케이스
    // sorted[0]와 sorted[1] 사이를 잇는 선 위에 next가 존재하는 경우
    // ex) sorted[0] : (0, 0), sorted[1] : (3, 0), next : (1, 0)
    // (Sort 함수 특성상 탐색 첫 단계에서만 해당 경우가 발생할 수 있기 때문에 Stack이 비어있음)
    else
    {
        stack.Push(item2);
        stack.Push(item1);
        idx++;
    }
}

return stack.Reverse().ToList();

 

코드

GitHub - jaywapp/Jaywapp.Algorithm