Convex Hull

kalpaca·2022년 7월 9일
0

Convex Hull(볼록껍질)은 배치된 모든 점을 모두 둘러쌀 수 있는 최소 면적을 이루는 점의 집합을 의미한다.
말이 어렵지만 그냥 모든 점을 둘러싸는 테두리라고 생각하면 쉽다.

이 또한 CCW로 풀 수 있다.
y좌표가 작은 순, x좌표가 작은 순으로 정렬하고
정렬된 맨 앞의 점을 기준으로 시계 반대방향으로 다시 정렬한다.
그리고 stack을 사용하여 직전 2개 점과 이번 점의 방향이 시계 반대 방향인 경우만 stack에 추가한다.
직전 2개 점과 이번 점의 방향이 시계 방향이라면, 직전 점이 Convex Hull을 이루는 점이 아니라는 뜻이므로, stack에서 제거 후 다시 확인한다.

이렇게 모든 점을 확인하면 stack에는 Convex Hull을 이루는 점만 남게 된다.

코드는 아래와 같다. 참고로 나는 최대한 직접 자료구조를 구현해서 사용하려고 한다.

#define MAXN 10000		// 점의 개수

typedef long long ll;

/********** 구조체 구현 **********/
struct Point {
	int x;
    int y;
    
    // 연산자 오버로딩
    Point operator-(Point other) {
    	Point ret;
        ret.x = this->x - other.x;
        ret.y = this->y - other.y;
        
        return ret;
    }
};

// 편의상 배열로 스택 구현
struct Stack {
	Point data[MAXN];
    int stackTop;
    
    void init() { stackTop = 0; }
    
    bool isEmpty() { return stackTop == 0; }
    
    int getSize() { return stackTop; }
    
    void push(Point newData) { data[stackTop++] = newData; }
    
    Point pop() { data[--stackTop]; }
    
    Point top() { return data[stackTop - 1]; }
};

/********** 전역변수 선언 **********/

Point points[MAXN];		// Point가 담겨있는 배열 -> arr
Point temp[MAXN];		// merge sort를 위한 임시 배열
Stack stack;

Point base;		// 시계 반대방향 정렬 시 사용될 기준

/********** Util 함수 구현 **********/

ll ccw(Point a, Point b) {
	return a.x * b.y - a.y * b.x;
}

ll ccw(Point base, Point a, Point b) {
	return ccw(a - base, b - base);
}

// base -> a -> b 가 시계 반대방향인지 확인하는 함수
bool isTurnLeft(Point base, Point a, Point b) {
	return ccs(base, a, b) > 0;
}

// 점 a와 점 b 사이의 거리 (제곱근 X)
ll getDistance(Point a, Point b) {
	ll diffX = a.x - b.x;
    ll diffY = a.y - b.y;
    
    return diffX * diffX + diffY * difFY;
}

// y 좌표가 작은 순으로, 같다면 x 좌표가 작은 순으로 정렬
// 앞의 점의 우선순위가 높다면 true
bool cmpYX(Point a, Point b) {
	int cmp = a.y - b.y;
    if(cmp == 0) cmp = a.x - b.x;
    
    return cmp < 0;
}

// base를 기준으로, 시계 반대방향으로 정렬
// 앞의 점이 더 각도가 작다면 true
bool cmpCCW(Point a, Point b) {
	ll res = ccw(base, a, b);
    // 일직선이라면, base에서 가까운 점이 우선
    if(res == 0) return getDistance(base, a) < getDistance(base, b);
    
    return res > 0;
}

// 주어진 배열을 주어진 compare 함수에 따라 merge sort
void mergeSort(Point arr[], int start, int end, bool (*compare)(Point, Point)) {
	if(start >= end) return;
    
    // Divide
    int mid = (start + end) >> 1;
    mergeSort(arr, start, mid, compare);
    mergeSort(arr, mid+1, end, compare);
    
    // Merge
    int left = start;
    int right = mid + 1;
    int idx = start;
    while(left <= mid && right <= end) {
    	temp[idx++] = compare(arr[left], arr[right]) ?
        			  arr[left++] : arr[right++];
    }
    
    // 왼쪽 배열이 남은 경우
    while(left <= mid) temp[idx++] = arr[left++];
    
    // 오른쪽 배열이 남은 경우
    while(right <= end) temp[idx++] = arr[right++];
    
    // temp에서 arr로 원상복구
    for(int i=start; i<=end; i++) arr[i] = temp[i];
}

/********** Convex Hull 구현 **********/

// arr[]: 점들이 담겨있는 배열
// N: 점의 전체 개수
void convexHull(Point arr[], int N) {
	// 1. 좌표 순으로 정렬
    mergeSort(arr, 0, N-1, cmpYX);
    
    // 2. base 기준으로 시계 반대방향 정렬
    base = arr[0];
    mergeSort(arr, 1, N-1, cmpCCW);
    
    // 3. Stack 초기화 -> 기본으로 점 2개 넣고 시작
    stack.init();
    stack.push(arr[0]);
    stack.push(arr[1]);
    
    // 4. Convex Hull 찾기 -> 모든 점을 한 번씩 확인
    for(int i=2; i<N; i++) {
    	while(stack.getSize() >= 2) {
        	Point first = stack.pop();	// 직전 점
            Point base = stack.top();	// 2개 전의 점 (기준 점)
            
            // base -> first -> arr[i] 방향이 시계 반대방향인지 확인
            if(isTurnLeft(base, first, arr[i]) {
            	stack.push(first);		// 뺐으니까 원상복구
                break;
            }
        }
        // stack에 현재 점 추가
        stack.push(arr[i]);
    }
    
    // 5. 이 시점에서 stack에는 Convex Hull을 이루는 점들만 들어있다.
}

0개의 댓글