CCW(Counter Clock Wise) 알고리즘

CCW(Counter-Clockwise) 알고리즘

은 2차원 평면상에서 세 점의 방향을 판별하는 알고리즘

주 사용 분야

이컴퓨터 그래픽스, 기하학적 문제, (혹은 알고리즘 풀 때...)

https://www.acmicpc.net/problem/2162

2162번: 선분 그룹

기본 개념

알고리즘의 기본 아이디어는 벡터의 외적(크로스 프로덕트)을 이용.

  - 벡터의 외적은 두 벡터가 이루는 평행사변형의 넓이를 계산.

CCW의 과정

1. 입력으로 주어진 세 점을 A, B, C라고 합니다.
2. 벡터 AB와 벡터 AC의 외적을 계산합니다.
3. 외적의 결과값을 이용하여 세 점의 방향을 판별합니다.

• 만약 AB와 AC의 외적이 양수 ( = 벡터 AB와 벡터 AC가 이루는 각이 반시계 방향)
  -> 점 A, B, C는 반시계 방향으로 배열되어 있습니다.
  => 이 경우 CCW 알고리즘은 1을 반환합니다.
• 반대로, AB와 AC의 외적이 음수 ( = 벡터 AB와 벡터 AC가 이루는 각이 시계 방향)
   -> 점 A, B, C는 시계 방향으로 배열되어 있습니다.
  => 이 경우 CCW 알고리즘은 -1을 반환합니다.
• 마지막으로, AB와 AC의 외적이 0 (A, B, C는 일직선상에 위치)
  => CCW 알고리즘은 0을 반환합니다.