APS.03 Geometric Problems

1. CCW란?

세 점 A, B, C가 주어졌을 때 이 점들이 반시계 방향으로 배치되어 있는지 판별하는 알고리즘이다.

$$CCW(A, B, C) = (B_x - A_x)(C_y - A_y) - (B_y - A_y)(C_x - A_x)$$

• 결과 > 0 → 반시계방향 (CCW)
• 결과 < 0 → 시계방향 (CW)
• 결과 = 0 → 세 점이 일직선 (Collinear)

def ccw(A, B, C):
    return (B[0]-A[0]) * (C[1]-A[1]) - (B[1]-A[1]) * (C[0]-A[0])

2. 외적(Cross Product)

CCW 공식 $x_1y_2 - x_2y_1$ 은 3D 외적의 z성분이다.

두 벡터를 3D로 확장하면 (z=0):

$$\mathbf{a} \times \mathbf{b} = (0,\ 0,\ x_1y_2 - x_2y_1)$$

x, y 성분이 0이므로 z성분만 남고, 그 부호가 회전 방향을 결정한다.

평행사변형 넓이

외적의 크기 = 두 벡터가 만드는 평행사변형의 넓이

$$|\mathbf{a} \times \mathbf{b}| = |\mathbf{a}||\mathbf{b}|\sin\theta$$

두 공식이 같다는 증명: $\mathbf{a} = (|\mathbf{a}|\cos\alpha,\ |\mathbf{a}|\sin\alpha)$ 로 놓으면

$$x_1y_2 - x_2y_1 = |\mathbf{a}||\mathbf{b}|(\cos\alpha\sin\beta - \sin\alpha\cos\beta) = |\mathbf{a}||\mathbf{b}|\sin(\beta - \alpha)$$

즉 $x_1y_2 - x_2y_1$ 은 좌표 계산용, $|\mathbf{a}||\mathbf{b}|\sin\theta$ 는 기하학적 해석용으로 수학적으로 동일하다.

2D vs 3D 외적

부호 결정 원리

2D에서 z축은 화면을 수직으로 뚫는 방향이다. 오른손 법칙(convention)에 의해:

• 반시계 회전 → 엄지 화면 밖(+z) → 외적 양수
• 시계 회전 → 엄지 화면 안(-z) → 외적 음수

이는 수학적 증명이 아닌 오른손 좌표계로의 약속이다.

3. 선분 교차 판별

핵심 아이디어: Straddle

한 선분이 다른 선분의 직선을 “걸치는가(straddle)” 를 CCW로 판별한다.

$$d_1 = CCW(p_1, p_2, p_3), \quad d_2 = CCW(p_1, p_2, p_4)$$

$$d_1 \cdot d_2 < 0 \implies p_3, p_4 \text{ 가 직선 } p_1p_2 \text{ 의 양쪽}$$

조건 하나만으로는 부족하다. 직선 기준이라 선분이 짧으면 교점에 못 미칠 수 있기 때문이다. 반대쪽도 확인해야 한다:

$$d_3 = CCW(p_3, p_4, p_1), \quad d_4 = CCW(p_3, p_4, p_2)$$

최종 규칙

두 선분은 다음 중 하나를 만족하면 교차한다.

Case 1. General — $d_1 \cdot d_2 < 0$ AND $d_3 \cdot d_4 < 0$

Case 2. Collinear — $d$ 값 중 하나라도 0이면, 해당 끝점이 다른 선분 위에 있는지 체크

$$\text{onSeg}(p, q, r): \quad \min(p_x, q_x) \le r_x \le \max(p_x, q_x) \quad \text{AND} \quad \min(p_y, q_y) \le r_y \le \max(p_y, q_y)$$

def on_segment(p, q, r):
    return (min(p[0],q[0]) <= r[0] <= max(p[0],q[0]) and
            min(p[1],q[1]) <= r[1] <= max(p[1],q[1]))

def intersects(p1, p2, p3, p4):
    d1 = ccw(p1, p2, p3);  d2 = ccw(p1, p2, p4)
    d3 = ccw(p3, p4, p1);  d4 = ccw(p3, p4, p2)

    if d1*d2 < 0 and d3*d4 < 0: return True

    if d1 == 0 and on_segment(p1, p2, p3): return True
    if d2 == 0 and on_segment(p1, p2, p4): return True
    if d3 == 0 and on_segment(p3, p4, p1): return True
    if d4 == 0 and on_segment(p3, p4, p2): return True

    return False

4. 볼록 껍질 (Convex Hull)

여러 점들을 모두 포함하는 가장 작은 볼록 다각형이다.

핵심 원리 (두 알고리즘 공통)

최신 세 점 A, B, C에서:

$$CCW(A, B, C) > 0 \implies \text{반시계 → B 유지}$$ $$CCW(A, B, C) \le 0 \implies \text{시계 or 일직선 → B 제거}$$

B가 새 껍질이 되는 게 아니라, 볼록성을 깨는 점 B를 제거하는 것이다.

Monotone Chain

아이디어: x좌표 정렬 → 아래 껍질(왼→오) → 위 껍질(오→왼) → 합치기

위아래를 나누는 이유: 한 방향만 훑으면 위/아래 경계를 동시에 처리하다 오목한 부분이 생긴다. 각자 한 방향만 담당하면 CCW 조건 하나로 깔끔하게 처리된다.

def monotone_chain(points):
    points = sorted(set(points))
    lower = []
    for p in points:
        while len(lower) >= 2 and ccw(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and ccw(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]

Graham Scan

아이디어: 가장 아래 점 기준 → 극각(각도) 순 정렬 → 반시계 한 바퀴

def graham_scan(points):
    pivot = min(points, key=lambda p: (p[1], p[0]))
    sorted_pts = sorted(points, key=lambda p: math.atan2(p[1]-pivot[1], p[0]-pivot[0]))
    hull = []
    for p in sorted_pts:
        while len(hull) >= 2 and ccw(hull[-2], hull[-1], p) <= 0:
            hull.pop()
        hull.append(p)
    return hull

두 알고리즘 비교

결과는 동일하다. Monotone Chain이 구현이 더 단순해서 실무에서 선호된다.