[기하] 기하

✔ 기하

기하 알고리즘이란?

• 점, 선, 다각형, 원과 같이 각종 기하학적 도형을 다루는 알고리즘
• 실제 코딩 테스트에서의 기하 알고리즘은 모두 CCW라는 기하학적 성질을 이용해 풀이

CCW란?

• 평면상의 3개의 점과 관련된 점들의 위치 관계를 판단하는 알고리즘

CCW 공식

• 세 점을 A(X₁, Y₁), B(X₂, Y₂), C(X₃, Y₃) 라고 가정했을 때, CCW = (X₁Y₂+ X₂Y₃+ X₃Y₁) - (X₂Y₁+ X₃Y₂, X₁Y₃)
• 세 점이 주어졌을 때 CCW 공식을 사용해 세 점에 관한 다양한 관계를 도출할 수 있음
  • CCW는 부호에 따라 다른 의미를 가짐
    CCW 결과 < 0 : 시계 방향 
    CCW 결과 == 0 : 일직선
    CCW 결과 > 0 : 반시계 방향
  • 부호와 별개로 CCW 결과의 절댓값은 세 점의 벡터의 외적값을 나타냄
  • CCW의 절댓값을 절반으로 나누면 세 점으로 이뤄진 삼각형의 넓이를 나타냄
    즉, |CCW 절댓값| / 2는 세 점으로 이뤄진 삼각형의 넓이