CCW - Counter Clockwise, 벡터의 외적

좌표만으로 넓이를 구해야 하는 경우가 있다

 간혹 알고리즘 문제를 풀 때 주어진 좌표만으로 넓이를 구해야 하는 경우가 있습니다. 일단적인 직사각형이라고 하면 쉽게 구할 수 있으나 간혹 5각형 이상의 다각형들이 나오기 때문에 이를 위한 알고리즘이 필요하게 됩니다.

 이 때 사용하게 되는 알고리즘이 CCW (Counter Clockwise)로 백터의 외적을 이용해서 넓이를 구하는 공식입니다. 외적에 대한 내용은 수학과 관련한 이야기니 코드적으로 알아볼 것만 보겠습니다.

 

 

CCW

CCW = { (x1 * y2) + (x2 * y3) + (x3 * y1) } - { (y1 * x2) + (y2 * x3) + (y3 * x1) } 

위 공식이 두 벡터를 통해서 방향성을 구한 것입니다. CCW의 값에 따라 방향이 정해지게 되는 것이죠.

 

- CCW = 0 : 직선

- CCW < 0 : 반시계 방향

- CCW > 0 : 시계 방향

 

 그리고 저기서 나오는 CCW를 나누기 2 하면 삼각형의 넓이를 구할 수 있는 것이죠.

 

 

CCW를 통해서 어떻게 다각형의 넓이를 구하나

 모든 다각형은 3각형을 한개 이상 포함하고 있습니다. 예를 들어 아무 다각형이나 그려보고 한 점을 기준으로 잡고 그 점에서 모든 점으로 가는 선을 그으면 안에 있는 삼각형들이 전부 나오게 됩니다.

 이를 이용해 코드로 옮기게 되면 

 

double CCW(double x1, double y1, double x2, double y2){
    double rVal = (spot[0].first * y1) + (x1 * y2) + (x2 * spot[0].second);
    rVal += (-spot[0].second * x1) - (y1 * x2) - (y2 * spot[0].first);
    rVal /= 2;
    return rVal;
}

int main(){
    for(int i = 1; i < t; i++)
        res += CCW(spot[i-1].first, spot[i-1].second, spot[i].first, spot[i].second);
}

 

 위와 같은 형태가 됩니다.

 

 코드에서는 spot의 0번 인덱스를 기준으로 잡고 CCW를 구한 것이며 이후 1번 인덱스부터 점을 옮겨가면서 다각형 내 삼각형 넓이를 전부 구해 더하는 과정인 것입니다.

 

 

 

추천 문제

 

11758번: CCW

 

2166번: 다각형의 면적

 

- 풀이

백준 2166 다각형의 면적 - C++, 벡터의 내적