선분 교차 (Line Segment Intersection)

정의

선분 교차 판정 (Line Segment Intersection) 은 2D 평면 위 두 선분 AB 와 CD 가 서로 교차하는지 O(1) 에 판정하는 기하 연산. CCW (Counter-Clockwise) 벡터 외적만으로 이루어짐.

문제 상황과 동기

두 선분의 교차 여부는 기하 문제의 가장 기본적인 빌딩 블록.

• naive: 모든 선분 쌍 O(N^2) 검사. N=10^3 이상에서 터짐.
• O(1) CCW 판정: CCW 4 회로 교차 여부를 바로 알 수 있음.

핵심 통찰: 각 선분의 양 끝점이 상대 선분의 양 옆에 있는지 확인. 즉, CCW(A,B,C) 와 CCW(A,B,D) 의 부호가 다른지, 동시에 CCW(C,D,A) 와 CCW(C,D,B) 의 부호가 다른지.

활용: Convex Hull, 선분 그룹 (DSU), Sweeping 의 기초 연산.

시각화

핵심 아이디어

세 점의 CCW 값을 구하는 cross product:

ccw(a, b, c) = (b.x - a.x)(c.y - a.y) - (b.y - a.y)(c.x - a.x)

• > 0 : 반시계 (좌회전)
• < 0 : 시계 (우회전)
• = 0 : 일직선 (collinear)

두 선분 AB, CD 가 교차하는 조건:

ccw(a,b,c) * ccw(a,b,d) <= 0  AND
ccw(c,d,a) * ccw(c,d,b) <= 0

즉, A-B 기준으로 C 와 D 가 서로 다른 쪽에 있고 (또는 하나가 선 위), C-D 기준으로 A 와 B 가 서로 다른 쪽에 있음.

Collinear (네 점이 모두 일직선) 인 경우는 projection range check 로 겹침 판정.

알고리즘

intersect(a, b, c, d):
    ab = ccw(a,b,c) * ccw(a,b,d)
    cd = ccw(c,d,a) * ccw(c,d,b)

    if ab == 0 and cd == 0:
        // 모두 일직선: x/y projection 이 겹치는지 확인
        if a.x > b.x: swap(a,b)
        if c.x > d.x: swap(c,d)
        if max(a.x,c.x) > min(b.x,d.x): return false
        if a.y > b.y: swap(a,b)
        if c.y > d.y: swap(c,d)
        return max(a.y,c.y) <= min(b.y,d.y)

    return ab <= 0 and cd <= 0

구현

// Line segment intersection, O(1)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
​
struct Point { ll x, y; };
​
ll ccw(Point a, Point b, Point c) {
  ll ret = (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
  if (ret > 0) return 1;
  if (ret < 0) return -1;
  return 0;
}
​
bool intersect(Point a, Point b, Point c, Point d) {
  ll ab = ccw(a,b,c) * ccw(a,b,d);
  ll cd = ccw(c,d,a) * ccw(c,d,b);
  if (ab == 0 && cd == 0) {
      if (a.x > b.x) swap(a,b);
      if (c.x > d.x) swap(c,d);
      if (max(a.x,c.x) > min(b.x,d.x)) return false;
      if (a.y > b.y) swap(a,b);
      if (c.y > d.y) swap(c,d);
      return max(a.y,c.y) <= min(b.y,d.y);
  }
  return ab <= 0 && cd <= 0;
}
​
int main() {
  Point a{1,1}, b{7,3}, c{2,4}, d{6,1};
  cout << (intersect(a,b,c,d) ? "YES" : "NO") << "\n";
  Point e{0,0}, f{3,3}, g{1,1}, h{2,2};
  cout << (intersect(e,f,g,h) ? "YES" : "NO") << "\n";
}

# CCW-based line segment intersection
def ccw(ax, ay, bx, by, cx, cy):
  ret = (bx-ax)*(cy-ay) - (by-ay)*(cx-ax)
  if ret > 0: return 1
  if ret < 0: return -1
  return 0
​
def intersect(ax, ay, bx, by, cx, cy, dx, dy):
  ab = ccw(ax,ay,bx,by,cx,cy) * ccw(ax,ay,bx,by,dx,dy)
  cd = ccw(cx,cy,dx,dy,ax,ay) * ccw(cx,cy,dx,dy,bx,by)
  if ab == 0 and cd == 0:
      if (ax, ay) > (bx, by): ax, bx = bx, ax; ay, by = by, ay
      if (cx, cy) > (dx, dy): cx, dx = dx, cx; cy, dy = dy, cy
      return max(ax, cx) <= min(bx, dx) and max(ay, cy) <= min(by, dy)
  return ab <= 0 and cd <= 0
​
print("YES" if intersect(1,1, 7,3, 2,4, 6,1) else "NO")
print("YES" if intersect(0,0, 3,3, 1,1, 2,2) else "NO")

import java.util.*;
public class Main {
  static int ccw(long ax, long ay, long bx, long by, long cx, long cy) {
      long ret = (bx-ax)*(cy-ay) - (by-ay)*(cx-ax);
      if (ret > 0) return 1;
      if (ret < 0) return -1;
      return 0;
  }
​
  static boolean intersect(
      long ax, long ay, long bx, long by,
      long cx, long cy, long dx, long dy
  ) {
      int ab = ccw(ax,ay,bx,by,cx,cy) * ccw(ax,ay,bx,by,dx,dy);
      int cd = ccw(cx,cy,dx,dy,ax,ay) * ccw(cx,cy,dx,dy,bx,by);
      if (ab == 0 && cd == 0) {
          if (ax > bx || (ax == bx && ay > by)) {
              long t; t=ax; ax=bx; bx=t; t=ay; ay=by; by=t;
          }
          if (cx > dx || (cx == dx && cy > dy)) {
              long t; t=cx; cx=dx; dx=t; t=cy; cy=dy; dy=t;
          }
          return (Math.max(ax,cx) <= Math.min(bx,dx) &&
                  Math.max(ay,cy) <= Math.min(by,dy));
      }
      return ab <= 0 && cd <= 0;
  }
​
  public static void main(String[] args) {
      System.out.println(intersect(1,1,7,3,2,4,6,1) ? "YES" : "NO");
      System.out.println(intersect(0,0,3,3,1,1,2,2) ? "YES" : "NO");
  }
}

YES
YES

복잡도

변형 / 활용

1. 선분 그룹 (Union-Find)

N 개 선분의 교차 관계를 DSU 로 묶으면 연결된 컴포넌트로 그룹화 가능. BOJ 2162.

2. 직선과의 교차

무한 직선과 선분의 교차: ccw(A,B,C) == 0 조건을 제거하고 projection 만 체크.

3. 교차점 좌표 구하기

두 직선의 교점을 parameter form 으로 직접 계산. collinear 가 아닐 때만.

t = cross(C-A, D-C) / cross(B-A, D-C)
P = A + t * (B - A)

4. 선분 교차 개수 (Sweep)

N 개 선분의 모든 교차점을 찾는 Sweeping 알고리즘. O((N+K) log N). Bentley-Ottmann.

함정

1. 정수 오버플로우

CCW 에서 (b.x-a.x) * (c.y-a.y) 는 10^6 * 10^6 = 10^12 로 int (32-bit) 범위 초과. long long 필요.

2. Collinear 겹침 처리

네 점이 일직선 위에 있을 때 ccw 만으로는 겹침 여부를 알 수 없음. Projection range check 필수.

3. 끝점 접촉

한 선분의 끝점이 다른 선분 위에 있는 경우 (< 0 조건) 교차로 인정. ccw() * ccw() < 0 대신 <= 0 사용.

BOJ 연습 문제

참고

• CCW (시계/반시계 판정)
• Convex Hull (CCW 의 확장)
• Sweeping (N 개 선분 교차)