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

지난 글에서 외적으로 볼록 껍질을 만들었습니다. 이번 글에서는 외적의 또 다른 대표 응용, 두 선분의 교차 판정을 다룹니다. 단순해 보이지만 끝점이 닿는 경우, 한 선분이 다른 선분 위에 일직선으로 겹치는 경우 등 경계 사례가 많아 정확히 구현하기 까다로운 문제입니다. 핵심 도구는 역시 외적(ccw) 하나입니다.

핵심 아이디어: 서로 갈라놓기

두 선분 AB와 CD가 교차하려면, AB가 점 C와 D를 양쪽으로 갈라놓고, 동시에 CD가 점 A와 B를 양쪽으로 갈라놓아야 합니다. “갈라놓는다”는 것은 외적 부호가 서로 다르다는 뜻입니다.

선분 교차의 세 가지 경우

이를 네 개의 외적으로 표현합니다.

d1 = ccw(C, D, A)    d2 = ccw(C, D, B)
d3 = ccw(A, B, C)    d4 = ccw(A, B, D)

A와 B가 직선 CD의 반대쪽이면 d1과 d2의 부호가 다르므로 d1·d2 < 0입니다. 마찬가지로 d3·d4 < 0이면 C와 D가 직선 AB의 반대쪽입니다. 두 조건이 동시에 성립하면 두 선분은 내부에서 확실하게 교차합니다.

def ccw(a, b, c):
    return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])

def sign(x):
    return (x > 0) - (x < 0)

경계 사례: 일직선과 끝점 접촉

위의 d1·d2 < 0 조건은 외적이 0이 되는 경우, 즉 점이 직선 위에 정확히 놓인 상황을 놓칩니다. 끝점이 다른 선분에 닿거나, 두 선분이 일직선으로 겹치는 경우가 여기 해당합니다.

판정 로직과 일직선 예외

이때는 외적이 0인 점이 상대 선분의 범위 안에 있는지를 따로 확인합니다. 일직선 위에서의 포함 여부는 바운딩 박스 비교로 충분합니다.

def on_segment(a, b, p):
    # p가 직선 ab 위에 있다고 가정, 선분 범위 안인지
    return (min(a[0], b[0]) <= p[0] <= max(a[0], b[0]) and
            min(a[1], b[1]) <= p[1] <= max(a[1], b[1]))

전체 판정 함수

일반 교차와 경계 사례를 모두 합치면 다음과 같습니다.

def segments_intersect(a, b, c, d):
    d1 = sign(ccw(c, d, a))
    d2 = sign(ccw(c, d, b))
    d3 = sign(ccw(a, b, c))
    d4 = sign(ccw(a, b, d))

    # 일반 교차: 양쪽 모두 부호가 엇갈림
    if d1 * d2 < 0 and d3 * d4 < 0:
        return True

    # 일직선/끝점 접촉
    if d1 == 0 and on_segment(c, d, a): return True
    if d2 == 0 and on_segment(c, d, b): return True
    if d3 == 0 and on_segment(a, b, c): return True
    if d4 == 0 and on_segment(a, b, d): return True

    return False

sign으로 외적 값을 −1, 0, +1로 정규화하면 오버플로 걱정 없이 곱의 부호만 비교할 수 있습니다. 입력이 정수면 이 함수 전체가 정수 연산만으로 동작해 부동소수점 오차가 전혀 없습니다.

바운딩 박스 빠른 기각

선분이 매우 많아 모든 쌍을 검사해야 한다면, 외적을 계산하기 전에 바운딩 박스가 겹치는지 먼저 봅니다. 두 선분의 x 구간이나 y 구간이 아예 분리돼 있으면 교차할 수 없으므로 즉시 기각합니다. 외적 네 번보다 훨씬 저렴한 사전 필터입니다.

def bbox_overlap(a, b, c, d):
    return (max(a[0],b[0]) >= min(c[0],d[0]) and
            max(c[0],d[0]) >= min(a[0],b[0]) and
            max(a[1],b[1]) >= min(c[1],d[1]) and
            max(c[1],d[1]) >= min(a[1],b[1]))

교점 좌표가 필요할 때

교차 여부가 아니라 실제 교점 좌표가 필요하면, 두 직선의 방정식을 외적(행렬식)으로 풀면 됩니다. 이 단계에서야 비로소 나눗셈이 등장하고 결과가 분수/실수가 됩니다.

def intersection_point(a, b, c, d):
    # 두 직선이 평행하지 않다고 가정
    r = (b[0]-a[0], b[1]-a[1])
    s = (d[0]-c[0], d[1]-c[1])
    rxs = r[0]*s[1] - r[1]*s[0]
    t = ((c[0]-a[0])*s[1] - (c[1]-a[1])*s[0]) / rxs
    return (a[0] + t*r[0], a[1] + t*r[1])

정리

선분 교차 판정의 원칙을 정리하면 다음과 같습니다.

상황	판정
일반 교차	`d1·d2 < 0` and `d3·d4 < 0`
끝점이 선분에 닿음	`di == 0` and 범위 안
일직선 겹침	외적 0 + 바운딩 박스
빠른 기각	바운딩 박스 미겹침
교점 좌표	직선 방정식 (나눗셈)

여부 판정은 정수로 끝내고, 좌표가 꼭 필요할 때만 실수로 넘어가는 습관이 오차 버그를 막습니다.

다음 글에서는 이런 선분·구간을 대량으로 다룰 때 강력한 패러다임, 평면을 한 방향으로 쓸어가며 처리하는 스위프 라인(sweep line)을 살펴봅니다.

지난 글: 볼록 껍질: 그레이엄 스캔과 모노톤 체인

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

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