CCW를 이용한 선분 교차 판정

CCW를 이용한 선분 교차 판정하기

문제

두 선분이 주어짐:

• 선분 AB
• 선분 CD

이 두 선분이 서로 교차(intersect) 하는지 판단하고 싶다.

교차의 의미:

• 내부에서 X자로 만나는 경우
• 끝점이 다른 선분 위에 닿는 경우

  → 모두 교차로 처리하는 게 일반적

핵심 아이디어

선분 교차의 핵심 조건:

점 C와 D가 선분 AB의 서로 다른 쪽에 있고

점 A와 B가 선분 CD의 서로 다른 쪽에 있으면

두 선분은 교차한다.

이걸 CCW로 판별한다.

공식

CCW 값 정의

ccw(A, B, C)
ccw(A, B, D)
ccw(C, D, A)
ccw(C, D, B)

기본 교차 조건 (일반적인 경우)

그리고

둘 다 만족하면 → 진짜 내부 교차 (X자 교차)

첫 번째 조건

ccw(A,B,C)와 ccw(A,B,D)의 부호가 다르면:

• C와 D가 선 AB의 서로 다른 쪽에 있음

  → CD가 AB를 가로지를 가능성 있음

두 번째 조건

ccw(C,D,A)와 ccw(C,D,B)의 부호가 다르면:

• A와 B가 선 CD의 서로 다른 쪽에 있음

  → AB가 CD를 가로지름

특수한 경우: 일직선 / 끝점 접촉

위 조건은 순수 교차(X자)만 잡는다.

하지만 실제 문제에서는 다음도 교차로 보는 경우도 있다:

• 한 점이 다른 선분 위에 정확히 놓인 경우
• 두 선분이 일직선 위에서 겹치는 경우

이 경우

그리고

를 확인하면 된다.