스위프 라인: 평면을 쓸어 기하 문제를 풀다

지난 글에서 두 선분의 교차를 외적으로 판정했습니다. 그런데 선분이 n개라면 모든 쌍을 검사하는 데 O(n²)가 듭니다. 교차점이 실제로 몇 개 없는데도 말이죠. 이번 글의 주제인 스위프 라인(sweep line)은 이런 기하 문제를 훨씬 똑똑하게 푸는 강력한 패러다임입니다. 가상의 직선으로 평면을 한 방향으로 쓸어가며, 그 선이 무언가를 만나는 순간에만 상태를 갱신합니다.

발상: 차원을 하나 줄이기

평면 전체를 한꺼번에 보는 대신, 수직선 하나를 왼쪽에서 오른쪽으로 천천히 움직인다고 상상해 봅시다. 이 선이 지나가는 동안 의미 있는 변화가 생기는 순간은 정해져 있습니다. 새 도형이 시작되거나, 끝나거나, 두 도형이 교차하는 지점입니다. 이런 순간을 사건(event)이라 부릅니다.

스위프 라인 개념

핵심은 연속적인 평면을 이산적인 사건들의 나열로 바꾼다는 것입니다. 사건은 x좌표 순으로 정렬돼 있고, 우리는 그 순서대로 하나씩 처리하며 현재 상태만 관리하면 됩니다. 2차원 문제가 “x를 따라가며 1차원 상태를 갱신”하는 문제로 줄어듭니다.

두 개의 자료구조

스위프 라인 알고리즘은 거의 항상 두 가지 자료구조를 함께 씁니다.

사건 큐와 활성 집합

사건 큐(event queue): 모든 사건을 x좌표 순으로 정렬한 목록. 보통 정렬된 배열이나 우선순위 큐로 둡니다. 교차점처럼 진행 중에 새로 발견되는 사건은 동적으로 삽입합니다.
활성 집합(active set / status structure): 지금 sweep line이 가로지르고 있는 도형들을, 보통 y좌표 순서로 유지하는 균형 이진 탐색 트리. 삽입·삭제·이웃 조회가 모두 O(log n)입니다.

events = sorted(all_events)      # (x, type, id)
active = OrderedStructure()      # y 순서 BST

for ev in events:
    if ev.type == "start":
        active.insert(ev.seg)
        # 위·아래 이웃과만 교차 검사
    elif ev.type == "end":
        active.erase(ev.seg)
    else:  # intersection
        report(ev)

예: 선분 교차 검출 (벤틀리–오트만)

n개의 선분 중 교차하는 쌍을 모두 찾는 문제를 봅시다. 순진하게는 O(n²)이지만, 핵심 통찰은 이것입니다. 두 선분이 교차하려면, 교차 직전 순간에 활성 집합에서 y좌표상 바로 인접해 있어야 한다. 따라서 모든 쌍이 아니라 인접한 이웃끼리만 교차를 검사하면 됩니다.

시작점 사건: 선분을 활성 집합에 넣고, 새로 생긴 위·아래 이웃과 교차를 검사한다.
끝점 사건: 선분을 빼고, 위아래로 새 이웃이 된 두 선분의 교차를 검사한다.
교차점 사건: 교차를 보고하고, 활성 집합에서 두 선분의 순서를 맞바꾼 뒤 새 이웃을 검사한다.

def check(a, b, x_now):
    # a, b가 sweep line 오른쪽에서 교차하면 사건 큐에 추가
    if segments_intersect(a, b):
        p = intersection_point(a, b)
        if p[0] >= x_now:
            event_queue.push((p[0], "cross", a, b))

교차점이 k개일 때 전체 복잡도는 O((n + k) log n)입니다. 교차가 적은 실제 데이터에서는 O(n²)보다 압도적으로 빠릅니다.

다른 대표 응용들

스위프 라인은 선분 교차에만 쓰이지 않습니다. 사건과 활성 집합의 정의만 바꾸면 다양한 문제에 적용됩니다.

문제	사건	활성 상태로 추적하는 것
선분 교차 검출	시작/끝/교차점	y정렬 활성 선분
직사각형 넓이 합집합	좌/우 변	덮인 y구간 길이 (세그먼트 트리)
가장 가까운 점 쌍	각 점	폭 d 안의 후보 점들
구간 스케줄·겹침 수	시작/끝	현재 열린 구간 개수

특히 직사각형 넓이의 합집합은 스위프 라인의 교과서적 예입니다. 수직 변을 사건으로 두고, 활성 집합으로 “현재 x에서 덮인 y구간의 총 길이”를 세그먼트 트리로 관리하면, 인접한 두 사건 사이의 넓이를 덮인 길이 × Δx로 누적해 전체 합집합 넓이를 구합니다.

구현 시 흔한 함정

동일 x좌표 사건의 순서: 같은 x에서 시작·끝·교차가 겹치면 처리 순서가 결과를 바꿉니다. 보통 (x, 우선순위)로 정렬해 안정적으로 만듭니다.
수직 선분: x가 변하지 않아 활성 집합 정렬 기준이 모호해집니다. 별도 처리하거나 약간 기울여 일반화합니다.
부동소수점 교차점: 교차점 좌표 비교에서 오차가 생깁니다. 가능하면 정수/유리수로 유지하거나 eps를 신중히 씁니다.
활성 집합 구현: 엄밀한 균형 BST가 필요하지만, 경쟁 프로그래밍에서는 std::set이나 정렬 리스트로 대체하기도 합니다.

스위프 라인은 “전체를 한 번에 보지 말고, 변화가 일어나는 지점만 순서대로 처리하라”는 발상 그 자체입니다. 이 사고방식은 기하뿐 아니라 구간 처리, 이벤트 시뮬레이션 등 여러 곳에서 반복적으로 등장합니다.

다음 글에서는 다시 기본 도형으로 돌아가, 다각형의 넓이를 외적의 합으로 구하는 신발끈 공식과 격자점을 세는 픽의 정리를 다룹니다.

지난 글: 선분 교차 판정: 외적과 바운딩 박스

다음 글: 다각형의 넓이: 신발끈 공식과 픽의 정리

읽어주셔서 감사합니다. 😊