CCW(CounterClockWise) 알고리즘

1. 개념

CCW는 외적을 이용해서 점 3개의 방향성을 나타내는 알고리즘이다.

즉, 세 점으로 이루어진 삼각형의 면적을 구하는 방법을 이용해서 방향성을 구한다.

우선 점 3개로 나타날 수 있는 경우는 총 3가지이다. 시계 방향, 일직선 방향, 반시계 방향 총 3가지이다.

2. 구현

어떠한 경우인지 알기 위해서 다음과 같은 식을 세운다.

여기서 S의 부호에 따라 경우를 3가지로 파악한다.

    1) S > 0 : 반시계 방향

    2) S = 0 : 일직선

    3) 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;
    }
}

* 출처 : https://www.acmicpc.net/blog/view/27

[CCW 예제 1 : http://gyutts.tistory.com/134]

[CCW 예제 2 : http://gyutts.tistory.com/135]