단순 다각형의 면적(Area of Simple Polygons)

평면상의 다각형(모서리의 교차가 없는 단순 다각형)의 면적을 구하는 것은 단순하지 않을 것처럼 보이지만 계산식은 무척이나 간단하게 주어진다. 기본적인 아이디어는 다각형에 임의의 점을 찍으면 이 점과 이웃한 두 개의 꼭짓점으로 형성이 되는 삼각형의 합으로 다각형을 분할할 수 있다. 분할된 삼각형의 면적을 구하여 합산하면 다각형의 면적을 구할 수 있다.

 

세 점 $\mathbf{P}\mathbf{,}\mathbf{Q}\mathbf{,}\mathbf{R}$(이 순서대로 반시계방향으로 배열)이 만드는 삼각형의 면적은

$$\text{삼각형의 면적}=\frac{1}{2}(\mathbf{R}-\mathbf{Q})\times (\mathbf{P}-\mathbf{Q});(\Rightarrow \text{시계 방향이면 면적이 음수})$$

로 주어지므로, 꼭짓점이 ${\mathbf{P}}_0(x_0,y_0),{\mathbf{P}}_1(x_1,y_1),....$(반시계 방향)으로 주어지는 $N$각형의 면적은 아래와 같이 주어진다. 

$$\begin{array}{rl}\text{다각형 면적}& =\sum \text{각 삼각형의 면적}\\ & =\frac{1}{2}\sum ({\mathbf{P}}_{i+1}-\mathbf{Q})\times ({\mathbf{P}}_i-\mathbf{Q})(\mathbf{Q}\text{는 임의의 점})\\ & =\frac{1}{2}\sum ({\mathbf{P}}_{i+1}\times {\mathbf{P}}_i-{\mathbf{P}}_{i+1}\times \mathbf{Q}+{\mathbf{P}}_i\times \mathbf{Q})\\ & =\frac{1}{2}\sum {\mathbf{P}}_{i+1}\times {\mathbf{P}}_i\\ & =\frac{1}{2}\sum (x_{i+1}{y}_i-x_i{y}_{i+1})\end{array}$$

이 결과는 $\mathbf{Q}$에 무관하다. 다각형의 꼭짓점이 시계 방향으로 정렬이 된 경우는 면적이 음수로 나온다(윈도 DC는 위-아래가 역전되어 있으므로 orientation이 반대로 보인다). 그리고 이 공식은 단순 다각형에만 적용이 되고 모서리의 교차가 있는 경우에는 적용이 되지 않는다.

double simplePolygonArea(const std::vector<CPoint>& point) {
    double area = 0;
    for (int i = 0, j = point.size()-1; i < point.size(); j = i++) 
        area += point[i].x * point[j].y - point[i].y * point[j].x;
    area /= 2;
    // return area;  // signed area;
    return area < 0 ? -area: area;
}