반평면 교집합 – 학습

1강 반평면들의 공통 영역 구하기 공식

문제

여러 반평면(half-plane) $a_i x + b_i y + c_i \le 0$ 의 공통 영역(볼록 다각형, 비거나 무한일 수 있음)을 구한다. 선형계획법의 실현가능영역, 로봇이 갈 수 있는 영역, 코어(core of polygon) 등에서 나온다. $O(n\log n)$ 에 교집합 다각형을 구하는 표준 알고리즘이 있다.

반평면의 표현

각 반평면을 "방향 벡터를 따라 진행할 때 왼쪽이 허용 영역"인 유향 직선으로 표현한다. 직선을 점 $$p$$ 와 방향 $\vec{d}$ 로 두면, 점 $$q$$ 가 허용되는 조건은 외적

$\vec{d} \times (q - p) \ge 0$

(즉 $$q$$ 가 직선의 왼쪽). 모든 반평면을 이 규약으로 통일하는 것이 첫 단계다.

정렬 + 덱(deque) 스위프

모든 반평면을 편각(방향 벡터의 각도) 순으로 정렬한다.
같은 방향이면 더 안쪽(엄격한) 것만 남긴다(중복 제거).
정렬 순서대로 덱에 넣되, 새 반평면이 덱의 마지막 두 직선의 교점을 허용하지 않으면 마지막을 pop, 처음 두 직선의 교점을 허용하지 않으면 앞을 pop. 즉 볼록 껍질 구성과 닮은 양끝 정리.
모든 반평면을 처리한 뒤, 덱 앞쪽 직선들이 덱 마지막에 대해 불필요해지는 것도 한 번 더 정리한다.

남은 덱의 인접 직선 교점들이 교집합 다각형의 꼭짓점이다.

정확성 직관

편각 정렬은 경계 직선들이 다각형을 돌아가는 순서와 일치한다. 새 직선이 들어올 때, 그 직선이 "잘라내는" 쪽의 꼭짓점(이전 교점)들을 양 끝에서 제거하면, 항상 현재까지의 실현가능영역의 볼록 경계가 유지된다. 한 직선은 덱에 한 번 들어가고 많아야 한 번 나가므로 스위프가 $$O(n)$$ (정렬이 지배적 $O(n\log n)$ ).

경계 사례

상황	처리
교집합이 빈 영역	덱이 모순(앞뒤가 서로를 배제)
무한(비유계) 영역	매우 큰 경계 박스를 넣어 유계화
평행·중복 직선	더 안쪽만 유지

복잡도

정렬 $O(n\log n)$ + 스위프 $$O(n)$$ . 결과 다각형 꼭짓점 수는 $$O(n)$$ .

2강 반평면 교집합 구현과 응용 공식

구현 (편각 정렬 + 덱)

반평면을 점 p 와 방향 dir(왼쪽이 허용)로 표현한다.

#include <bits/stdc++.h>
using namespace std;
typedef double T;
struct Pt { T x, y; };
Pt operator-(Pt a, Pt b){ return {a.x-b.x, a.y-b.y}; }
T cross(Pt a, Pt b){ return a.x*b.y - a.y*b.x; }

struct Half { Pt p, dir; double ang;        // 직선 위 한 점 p, 방향 dir
    Half(Pt p, Pt d): p(p), dir(d) { ang = atan2(d.y, d.x); } };

bool out(const Half& h, Pt q){ return cross(h.dir, q - h.p) < -1e-9; } // q가 오른쪽이면 배제

Pt inter(const Half& a, const Half& b){     // 두 직선의 교점
    T t = cross(b.p - a.p, b.dir) / cross(a.dir, b.dir);
    return {a.p.x + a.dir.x * t, a.p.y + a.dir.y * t};
}

vector<Pt> halfPlaneIntersection(vector<Half> h) {
    sort(h.begin(), h.end(), [](const Half& a, const Half& b){
        if (fabs(a.ang - b.ang) > 1e-9) return a.ang < b.ang;
        return cross(a.dir, b.p - a.p) < 0;     // 같은 각이면 안쪽 우선
    });
    // 같은 방향 중복 제거
    vector<Half> hs;
    for (auto& x : h)
        if (hs.empty() || fabs(hs.back().ang - x.ang) > 1e-9) hs.push_back(x);
    deque<Half> dq; deque<Pt> pts;
    for (auto& cur : hs) {
        while (!pts.empty() && out(cur, pts.back()))  { dq.pop_back();  pts.pop_back(); }
        while (!pts.empty() && out(cur, pts.front())) { dq.pop_front(); pts.pop_front(); }
        if (!dq.empty()) pts.push_back(inter(dq.back(), cur));
        dq.push_back(cur);
    }
    while (!pts.empty() && out(dq.front(), pts.back()))  { dq.pop_back();  pts.pop_back(); }
    if (dq.size() < 3) return {};                 // 비었거나 비유계
    pts.push_back(inter(dq.back(), dq.front()));
    return vector<Pt>(pts.begin(), pts.end());
}

자주 하는 실수

방향 규약 불일치. "왼쪽 허용" 을 모든 반평면에 일관되게 적용. 한 직선이라도 뒤집히면 결과가 깨진다.
편각 정렬 타이브레이크. 같은 각의 평행 직선 중 안쪽만 남겨야 한다.
유계화. 무한 영역이 답일 수 있으면 큰 경계 사각형 네 개의 반평면을 미리 넣어 유계로 만든다.
부동소수 eps. out/교점에서 적절한 eps. 정수 좌표면 분수/long double 로 정밀도 확보.

응용

문제	모델
2D 선형계획 실현가능영역	제약 = 반평면
다각형의 core(모든 점이 보이는 영역)	변마다 내부 반평면
최대 내접/이동 가능 영역	반평면 + 이분 탐색
켈리·시야 영역	차폐 반평면

LP와의 연결

2변수 선형계획의 목적함수 최적점은 반평면 교집합 다각형의 꼭짓점 중 하나다. 교집합을 구한 뒤 꼭짓점을 훑거나, 목적함수 방향의 반평면을 이분 탐색으로 끼워 최적값을 찾는다.