[Algorithm] CCW

CCW 알고리즘 결과값에 따른 방향을 표기하고 있다.

CCW(Counter Clock Wise) 알고리즘은 3개의 점을 이은 직선의 방향을 알 수 있는 알고리즘이다.

경우의 수는 총 3가지이며 양수, 0, 음수 값으로 방향을 알 수 있다.

특히 외적을 통하여 구하는 것이 특징인데, 외적 구하는 방법에 대해 확인해보자.

 

외적 구하는 방식

static int CCW(long x1, long y1, long x2, long y2, long x3, long y3){
    long dir = (x1 - x2) * (y2 - y3) - (x2 - x3) * (y1 - y2);
    return dir == 0 ? 0 : ( dir > 0 ? 1 : -1 );
}