[알고리즘] CCW (선분 교차 판별)

CCW : Counter Clock Wise

• 3개의 점 A, B, C가 있을 때 이 점 3개를 이은 직선의 방향을 알고자 할 때 유용한 기하 알고리즘
• 3가지 경우의 수
• 외적을 통하여 구할 수 있다.
  • 외적의 결과가 음수면 시계 방향
  • 직선은 0
  • 양수면 반시계 방향 

외적이란

• 두 벡터에 동시에 수직인 벡터를 찾는 연산
• 두 벡터에 동시에 수직인 벡터는 2개이므로 두 벡터의 순서로 방향을 결정

외적 계산

• i, j, k : x축, y축, z축 단위 벡터

선분 교차

• 교차할려면
  • A와 B는 CD를 기준으로 다른 영역에 있어야 한다. 즉, CCW 부호가 달라야 한다.
    • 하지만 반드시 교차는 아니다.
    • 양쪽에 대해 둘 다 방향이 달라야 실제로 교차함을 확인 가능

왼(교차), 오(교차X)

예외

• 네 점 중 세 점이 일직선
  • 하나의 점이 나머지 선분 사이에 있는지 확인

왼(교차) 오(교차X)

• 네 점이 일직선

---

<백준 문제>

https://chaemi720.tistory.com/305

[백준] 11758. CCW - Python