Half-Plane Intersection

2026년 6월 25일 · 수정 2026년 6월 25일 · 📖 약 3분 · 969자/단어 #algorithm #geometry #half-plane-intersection

정의

반평면 교집합 (Half-Plane Intersection) 은 N 개의 직선으로 정의된 반평면 ax + by + c <= 0 (또는 >= 0) 을 모두 만족하는 점들의 집합, 즉 볼록다각형 (convex polygon) 혹은 무한 영역 / 공집합을 구하는 기하 알고리즘.

문제 상황과 동기

각 반평면을 naive 하게 교집합하면 O(N^2). 즉, convex polygon 의 clipping 을 N 번 반복해야 한다. N=10^5 면 불가능.

핵심 통찰: 반평면을 각도(기울기) 순으로 정렬하고 deque 로 관리하면 convex hull 과 동일한 각도 정렬 + Amortized O(N) 테크닉 으로 O(N log N) 에 해결된다. Convex Hull 의 Graham scan 과 거의 같은 구조.

활용: 볼록다각형 내 최대 내접원, Minkowski 덧셈, 일부 LP (Linear Programming) 의 특수 케이스.

시각화

핵심 아이디어

각 반평면을 directed line p -> q 로 표현. valid side 는 항상 line 의 왼쪽 (CCW > 0). 각도 atan2(dy, dx) 순으로 정렬 후 deque 로 관리.

for each L in sorted order:
    while deque[-2] x deque[-1] NOT in L -> pop back
    while deque[0] x deque[1] NOT in L -> pop front
    push back L
마지막에 front/back 정리

각 반평면은 최대 한 번 push/pop. O(N).

알고리즘

halfplane_intersection(L):
    sort L by angle = atan2(dy, dx) (같은 angle: tight 한 것만 keep)
    deque = empty
    for each line in L:
        while |deque| >= 2 and cross(line, inter(deque[-2], deque[-1])) < 0:
            pop back
        while |deque| >= 2 and cross(line, inter(deque[0], deque[1])) < 0:
            pop front
        push back
    while |deque| >= 3 and cross(deque[0], inter(deque[-2], deque[-1])) < 0:
        pop back
    return [inter(deque[i], deque[(i+1)%|deque|]) for i]

구현

// Half-plane intersection, O(N log N)
#include <bits/stdc++.h>
using namespace std;
using ld = long double;
const ld EPS = 1e-9;
struct Pt { ld x, y; };
struct Line { Pt p, q; }; // valid: left side
ld cross(Pt a, Pt b) { return a.x*b.y - a.y*b.x; }
ld cross(Pt a, Pt b, Pt c) { return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x); }
Pt inter(Line a, Line b) {
  Pt va = {a.q.x-a.p.x, a.q.y-a.p.y};
  Pt vb = {b.q.x-b.p.x, b.q.y-b.p.y};
  Pt vc = {b.p.x-a.p.x, b.p.y-a.p.y};
  ld t = cross(vc, vb) / cross(va, vb);
  return {a.p.x + t*va.x, a.p.y + t*va.y};
}
ld angle(Line l) { return atan2(l.q.y-l.p.y, l.q.x-l.p.x); }
vector<Pt> halfplane(vector<Line> L) {
  sort(L.begin(), L.end(), [](Line a, Line b) { return angle(a) < angle(b); });
  deque<Line> dq;
  for (auto& l : L) {
      while (dq.size() >= 2 && cross(l.p, l.q, inter(dq[dq.size()-2], dq.back())) < EPS) dq.pop_back();
      while (dq.size() >= 2 && cross(l.p, l.q, inter(dq[0], dq[1])) < EPS) dq.pop_front();
      dq.push_back(l);
  }
  while (dq.size() >= 3 && cross(dq[0].p, dq[0].q, inter(dq[dq.size()-2], dq.back())) < EPS) dq.pop_back();
  vector<Pt> res;
  for (int i = 0; i < (int)dq.size(); i++) res.push_back(inter(dq[i], dq[(i+1)%dq.size()]));
  return res;
}
int main() {
  vector<Line> L = {{{0,0},{1,0}}, {{0,1},{0,0}}, {{6,0},{0,6}}, {{4,6},{-2,0}}};
  auto poly = halfplane(L);
  cout << fixed << setprecision(0);
  for (auto& p : poly) cout << "(" << p.x << ", " << p.y << ")\n";
}

# Half-plane intersection, O(N log N)
import math

class Pt:
  def __init__(self, x, y): self.x, self.y = x, y

def cross(a, b, c):
  return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x)

def inter(a, b):
  v1 = Pt(a[1].x-a[0].x, a[1].y-a[0].y)
  v2 = Pt(b[1].x-b[0].x, b[1].y-b[0].y)
  v3 = Pt(b[0].x-a[0].x, b[0].y-a[0].y)
  denom = v1.x*v2.y - v1.y*v2.x
  if abs(denom) < 1e-12: return None
  t = (v3.x*v2.y - v3.y*v2.x) / denom
  return Pt(a[0].x + t*v1.x, a[0].y + t*v1.y)

lines = [
  (Pt(0,0), Pt(1,0)), (Pt(0,1), Pt(0,0)),
  (Pt(6,0), Pt(0,6)), (Pt(4,6), Pt(-2,0))
]
lines.sort(key=lambda l: math.atan2(l[1].y-l[0].y, l[1].x-l[0].x))
dq = []
for l in lines:
  while len(dq) >= 2 and cross(l[0], l[1], inter(dq[-2], dq[-1])) < 0:
      dq.pop()
  while len(dq) >= 2 and cross(l[0], l[1], inter(dq[0], dq[1])) < 0:
      dq.pop(0)
  dq.append(l)

while len(dq) >= 3 and cross(dq[0][0], dq[0][1], inter(dq[-2], dq[-1])) < 0:
  dq.pop()

res = [inter(dq[i], dq[(i+1)%len(dq)]) for i in range(len(dq))]
for p in res:
  print(f"({p.x:.0f}, {p.y:.0f})")

// Half-plane intersection (basic, no deque in snippet)
import java.util.*;
import java.awt.geom.Point2D;

public class Main {
  static double cross(Point2D o, Point2D a, Point2D b) {
      return (a.getX()-o.getX())*(b.getY()-o.getY())
           - (a.getY()-o.getY())*(b.getX()-o.getX());
  }

  static Point2D inter(Point2D p1, Point2D q1, Point2D p2, Point2D q2) {
      double vx1 = q1.getX()-p1.getX(), vy1 = q1.getY()-p1.getY();
      double vx2 = q2.getX()-p2.getX(), vy2 = q2.getY()-p2.getY();
      double vx3 = p2.getX()-p1.getX(), vy3 = p2.getY()-p1.getY();
      double denom = vx1*vy2 - vy1*vx2;
      double t = (vx3*vy2 - vy3*vx2) / denom;
      return new Point2D.Double(p1.getX()+t*vx1, p1.getY()+t*vy1);
  }

  static double angle(Point2D p, Point2D q) {
      return Math.atan2(q.getY()-p.getY(), q.getX()-p.getX());
  }

  public static void main(String[] args) {
      Point2D.Double[][] lines = {
          {new Point2D.Double(0,0), new Point2D.Double(1,0)},
          {new Point2D.Double(0,1), new Point2D.Double(0,0)},
          {new Point2D.Double(6,0), new Point2D.Double(0,6)},
          {new Point2D.Double(4,6), new Point2D.Double(-2,0)}
      };
      Arrays.sort(lines, (a,b) -> Double.compare(
          angle(a[0],a[1]), angle(b[0],b[1])));
      // Deque simulation omitted for brevity
      for (int i = 0; i < 4; i++) {
          Point2D p = inter(lines[i][0], lines[i][1],
              lines[(i+1)%4][0], lines[(i+1)%4][1]);
          System.out.printf("(%.0f, %.0f)%n", p.getX(), p.getY());
      }
  }
}

결과

(0, 0)
(6, 0)
(2, 4)
(0, 2)

복잡도

항목	값
시간 (정렬)	O(N log N)
시간 (Deque)	O(N) (각 line 최대 1회 push/pop)
전체	O(N log N)
공간	O(N)

변형 / 활용

1. 볼록다각형 내 최대 내접원

Convex polygon 의 각 변을 안쪽으로 평행 이동 (offset) 하여 새로운 반평면들 생성. 그 교집합에 가장 큰 원이 들어갈 수 있는 중심점.

2. Minkowski Sum

두 볼록다각형 A, B 의 Minkowski sum A + B = {a + b | a in A, b in B}. 각 변의 방향별로 half-plane 으로 표현 가능.

3. LP (Linear Programming) 의 2D 특수 케이스

2변수 LP 는 half-plane intersection 으로 변환 가능. 후에 simplex 또는 Parametric Search 로 최적화.

함정

1. EPS 좌우 판정

cross(l.p, l.q, inter(...)) < EPS 로 반평면에 속하지 않음을 판정. EPS 를 너무 작게 잡으면 floating error 로 무한루프.

2. 무한 영역 / 공집합

결과가 유계 폴리곤이 아닐 수 있음. 빈 deque 나 2개 미만의 점이면 unbounded 또는 empty.

3. 평행 반평면

같은 각도의 반평면은 cross 값이 더 큰 (더 제약적인) 것만 유지.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 16872	Count the Half-Planes	(수집 안 됨)	kokoa-lab
BOJ 12795	Half-Plane	(수집 안 됨)	kokoa-lab
BOJ 20420	1차원 Half-Plane	(수집 안 됨)	kokoa-lab

참고

Convex Hull (비슷한 Deque 구조)
스위핑
선분 교차 판정

이 글의 용어 (4개)

병렬 이분 탐색 (Parallel Binary Search)algorithm: 정의 병렬 이분 탐색 (Parallel Binary Search, PBS) 은 Q 개의 쿼리를 각각 독립적으로 이분탐색하지 않고, 모든 쿼리의 이분탐색을 라운드별로 동시에 진행하…
볼록 껍질 (Convex Hull)algorithm: 정의 볼록 껍질 (Convex Hull) 은 주어진 점 집합 P 를 모두 포함하는 최소 크기의 볼록 다각형. 즉 P 의 어떤 점도 다각형 외부에 있지 않고, 다각형의 꼭짓점은 P…
선분 교차 (Line Segment Intersection)algorithm: 정의 선분 교차 판정 (Line Segment Intersection) 은 2D 평면 위 두 선분 AB 와 CD 가 서로 교차하는지 O(1) 에 판정하는 기하 연산. CCW (C…
스위핑 (Sweeping)algorithm: 정의 스위핑 (Sweeping) 은 시간 또는 공간 축 위의 이벤트를 정렬한 뒤, 한 방향으로 훑으며 상태를 갱신해 문제를 푸는 기법입니다. 선분 교차, 구간 합집합, 최대 겹침…