점 3개의 방향성을 나타내는 CCW

세 점 P1(x1, y1), P2(x2, y2), P3(x3, y3)가 있을 떄, 점 3개를 이은 선분은 어떤 방향성을 나타내게 될까요? 11758번 문제: CCW

가능한 경우의 수는 총 3가지가 있습니다. 반시계 방향, 시계 방향, 일직선. 시계 방향을 -1, 일직선을 0, 반시계 방향을 1이라고 했을 때, P1은 검정색, P2는 초록색, P3을 파란색으로 나타내면 아래 그림과 같습니다.

세 점으로 이루어진 삼각형의 면적을 구하는 방법을 이용해서 방향성을 구할 수 있습니다. $S$를 점 P1, P2, P3로 이루어진 삼각형의 면적이라고 했을 때

$$2 \times S =\begin{vmatrix} x_1 & y_1 & 1 \\ x_2 & y_2 & 1 \\ x_3 & y_3 & 1 \end{vmatrix} = (x_2 - x_1)(y_3-y_1) - (y_2-y_1)(x_3-x_1)$$

입니다.

여기서 S의 부호에 따라서, 다음과 같이 세 가지로 나눌 수 있습니다.

  • S > 0: 반시계 방향
  • S = 0: 일직선
  • S < 0: 시계 방향

코드로 나타내면 아래와 같습니다.

int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
    int temp = x1*y2+x2*y3+x3*y1;
    temp = temp - y1*x2-y2*x3-y3*x1;
    if (temp > 0) {
        return 1;
    } else if (temp < 0) {
        return -1;
    } else {
        return 0;
    }
}

댓글 댓글 쓰기