12-1. 기하 알아보기

기하의 핵심 이론: CCW

CCW(Counter-Clockwise)

• 평면상의 3개의 점과 관련됨 점들의 위치 관계를 판단하는 알고리즘
• 세 점을 기준으로 할 때 CCW의 공식은 다음과 같음
  • $A(X_1, Y_1)$, $B(X_2, Y_2)$, $C(X_3, Y_3)$
  • $CCW = (X_1Y_2 + X_2Y_3 + X_3Y_1) - (X_2Y_1+X_3Y_2+X_1Y_3)$

공식 도출 과정

1. 1번째 점을 뒤에 한 번 더 작성
2. 오른쪽 아래 방향 화살표 곱은 더하고, 왼쪽 아래 방향 화살표의 곱은 빼기

결과 해석

• 세 점의 벡터의 외적값을 나타냄
  • $|\text{CCW의 결과값}|/2$ = (세 점으로 이뤄진 삼각형의 넓이)