[기하] 볼록 다각형(Gift Wrapping, Graham Scan)

Convex Hull 알고리즘에서 사용할 클래스

const double PI = acos(-1.0);
struct Vector2{
   
    double x, y;

    explicit Vector2(double x_=0, double y_=0) : 
        x(x_), y(y_) {}
        
    bool operator < (const Vector2& b) const {
    	return (a.x==b.x) ? (a.y < b.y) : (a.x < b.x); 
   	}
    
    double norm() {
    	return hypot(x, y);
    }
	//외적
    double cross(const Vector2& b) const {
        return x * b.y - y * b.x;
    }
};

double ccw(Vector2 a, Vector2 b) {
	return a.cross(b);
}

// a->b->c로 이어지는 선분의 방향
double ccw(Vector2 a, Vector2 b, Vector2 c) {
	return ccw(b-a, c-a);
}

Graham Scan O(NlogN)

// 다각형의 꼭짓점들
vector<Vector2> edges; 
int n = edges.size();

// 1. 가장 아래, 그중 가장 왼쪽 점 찾기 O(N)
Vector2 pivot = edges[0];
    for (int i = 1; i < n; ++i) {
        if (edges[i].y < pivot.y) {
            pivot = edges[i];
        }
        else if (edges[i].y == pivot.y && edges[i].x < pivot.x)
            pivot = edges[i];
    }
// 2. 그 점을 기준으로, 이루는 각의 크기순으로 정렬(같을시 거리가까운 순) O(NlogN)
// 제일 아래, 그중 제일 왼쪽 점을 기준으로 잡았으므로
// 기준과 임의의 점이 이루는 각은 0~pi임을 알 수 있다.
// 따라서, 기준점은 정렬시 제일 첫번째 점으로 위치한다.
// ccw값은 0이고(ccw(p, p, ?) == 0), 거리도 0이라서 우선순위가 제일 앞선다.
sort(edges.begin(), edges.end(),
        [pivot](const Vector2& a, const Vector2& b) {
            int temp = ccw(pivot, a, b);
            if (temp == 0) {
                return dist(pivot, a) <= dist(pivot, b);
            }
            else {
                return temp > 0;
            }
        }
        );
// 3. 마무리 O(N)
// 제일아래,왼쪽 점에서 시작해서 반시계방향으로 스캔
vector<Vector2> hull;
int i = 0;
while (i < n) {
	// 우선 최소 2개는 들어있어야 ccw비교가 가능하다
	while (hull.size() < 2) hull.push_back(edges[i++]);
	// ccw값이 양수이면(볼록하면) hull의 후보에 넣는다
    // 음수라면, 이전에 넣은 꼭지점이 필요없다는 의미이기 때문에 pop
    // pop하다보면 꼭짓점이 2개미만이 되던가, 아니면 다시 ccw>0
    int temp = ccw([hull[(int)hull.size() - 2], hull.back(), edges[i]);
    if (temp > 0) 
        hull.push_back(edges[i++]);
    else 
        hull.pop_back();
}

볼록껍질에 포함된다는게 보장되기만 한다면 기준점 및 정렬 기준을 바꿔도 되지만, 신경쓸게 많다.
정렬 기준을 제일 아래점중 제일 왼쪽점으로 하면 편리한 점이 많다. 기준점과 임의의 다른 점이 이루는 각이 0~PI이기 때문에 CCW 비교 및 정렬하는데 혼란이 적다.

Gift Wrapping O(N^2)

// 다각형의 꼭짓점들
vector<Vector2> edges; 
int n = edges.size();

// Vector2의 < 연산자 활용해서 기준점 잡기
// 제일 왼쪽, 그중 제일 아래에서 시작해서 이번엔 시계방향으로
Vecotr2 pivot = *min_element(edges.begin(), edges.end());

// 알고리즘 시작
vector<Vector2> hull = {pivot};
while (true) {
	// cur(현재)점에서 제일 왼쪽 점을 찾는다
    // 무조건 볼록다각형에 포함되는 점만 찾으므로, cur과 이루는 각이
    // 볼록한 점 중에서 제일 왼쪽, 그중 제일 멀리 있는 점을 찾는다
    Vector2 cur = hull.back(), next = edges[0];
    for (int i=1; i<n; ++i) {
    	int temp = ccw(cur, next, edges[i]);
        // 대소비교가 목표이므로 맨해튼거리 사용해도 된다
        int dist = (edges[i]-cur).norm() - (next-cur).norm(); 
        // 더 볼록하거나(더 왼쪽에 있거나) 각은 같은데 더 멀리있으면 갱신
        if (temp > 0 || (temp==0 && dist>0))
        	next = edges[i];
    }
    // 시작점으로 돌아왔으면 끝
    if (next == pivot) break;
	hull.push_back(next);        
}

시간이 좀더 걸리지만 더 직관적이다. 정렬해두고 쭉 스캔하는 그라함 스캔과 달리 매번 "볼록 껍질에 무조건 포함되는" 점들만 찾아서 포함시킨다.

관련 문제

https://www.acmicpc.net/problem/1708

Reference

종만북