[CCW] Counterclockwise

목적

세 개의 노드를 연결하는 두 에지가 시계 방향으로 연결되어있는지, 시계 반대 방향으로 연결되어 있는지 판단한다.

아이디어

두 에지의 외적을 사용해서 구현한다.

• 외적 값이 양수 : 좌회전, 시계 반대 반향
• 외적 값이 음수 : 우회전, 시계 방향
• 외적 값이 0 : 세 노드가 같은 직선상에 존재한다.

구현

int ccw(int x1, int y1, int x2, 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; }
}

응용

• 두 선분의 교차 여부

두 선분의 양 끝점을 알고 있을 때, 선분 A 의 벡터를 기준으로 선분 B의 두 점이 서로 다른 방향에 있어야 하고, 선분 B의 벡터에 대해서도 A의 두 점을 검사해야 한다.

왼쪽의 경우 한 번만 검사해도 옮은 경우가 나오지만, 두 선분이 오른쪽과 같이 되어있는 경우 한 선분에 대해서만 검사하면 두 선분의 교차를 완벽하게 알아낼 수 없다.

예외사항

두 선분이 같은 직선 위에 있는 경우 CCW의 알고리즘은 실패한다. 이때는 두 선분이 접점을 따져서 문제의 조건에 부합하는지 판단해야 한다.