CCW (Counter Clock Wise)

CCW (Counter Clock Wise)

---

 CCW 란? 

  평면에 존재하는 세 점에 대해서 위치 관계를 알 수 있는 알고리즘이다. 좌표 내 임의의 점이 어떠한 선분을 기준으로 반시계방향에 있다면 양수, 시계방향에 있다면 음수, 선분의 연상선인 직선상에 있다면 0을 출력한다. 

---

 설명 

• 공식 :  CCW = (Bx - Ax) * (Cy - Ay) - (Cx - Ax) * (By - Ay) 

  CCW 의 값이 양수라면? : 점 C는 선분 AB의 반시계방향에 위치한다.

  CCW 의 값이 음수라면? : 점 C는 선분 AB의 시계방향에 위치한다.

  CCW 의 값이 0 이라면? : 점 C는 선분 AB의 직선상에 위치한다.

 

  위 예시 첨부 사진 상에선 점C 가 선분 AB의 반시계방향에 위치하므로 CCW 의 값은 양수가 된다.

---

   점 A, B, C 의 관계 

  A---B 선분을 점 A 에서 점 B 로 가는 벡터로 생각하였을 때 점 B 에서 점 C 로 가는 위치는 A ---> B 의 입장에서 반시계방향으로 가야한다. 

  ∴ CCW(A, B, C) > 0

 

   점 A, B, E 의 관계 

  A---B 선분을 기준으로 점 E 는 선분 A---B의 시계방향에 존재한다.

  ∴ CCW(A, B, E) < 0

 

   점 A, B, F 의 관계 

  A---B 선분을 기준으로 점 F 는 선분 A---B의 연장선 상에 놓여있다.

  ∴ CCW(A, B, F) = 0

---

 증명 

  이는 벡터의 외적을 활용한 알고리즘이다.

  이 경우 점 C 는 선분 AB의 반시계방향에 놓여있고, 이 때 CCW의 값은 양수가 나온다. 이는 벡터 AB 와 벡터 AC 의 외적값에 의해 결정이 된 값이다. 벡터 AB 를 u, 벡터 AC 를 v 라고 할 때 아래와 같이 벡터의 외적 공식을 사용할 수 있다.

 

 | u X v | = | u || v | sinθ 

 

  따라서, θ 의 값이 0˚ < θ < 180˚ 인 경우 ( 점 C 가 선분 AB의 반시계방향에 놓여있는 경우 ) 엔 sin θ 의 값이 양수가 되어 |u X v| 의 값은 양수, θ 의 값이 180˚ < θ < 360˚ 인 경우 ( 점 C 가 선분 AB의 시계방향에 놓여있는 경우 ) 엔 sin θ 의 값이 음수가 되어 |u X v| 의 값은 음수, θ 의 값이 0˚ 혹은 180˚ 인 경우 ( 점 C 가 선분 AB의 연장선상에 놓여있는 경우 ) 엔 sin θ 의 값이 0이 되어 |u X v| 의 값은 0이된다.

 

출처 : 벡터 외적 공식 (naver.com)

  외적 공식은 3차원 좌표에서 다뤄지지만, 벡터 u 와 벡터 v 의 z 값을 0 이라고 생각하여 외적값을 계산하면 되는 원리이다.

---

 Code 

#include <iostream>
#include <vector>
 
using namespace std;
 
struct coordinate {
    int x;
    int y;
};
 
int CCW(coordinate A, coordinate B, coordinate C) {
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
 
int main() {
    // ...
}

  좌표의 범위가 int형의 범위 밖으로 더 넓어지거나, 정수가 아닌 실수형 좌표값들을 다루는 상황들에 대해선 그 상황에 맞추어 int 형을 long long이나 double 과 같은 형태로 바꾸어 주면 된다.

---

 활용 

  이 공식은 "선분 교차" 문제에서 활용할 수 있다.