$O(N)$에 단순 다각형의 넓이 구하기¶

단순 다각형(즉, 자기 교차가 없으며 반드시 볼록일 필요는 없는 다각형)이 주어졌다고 합시다. 정점들이 주어졌을 때 그 넓이를 계산해야 합니다.

방법 1¶

모든 간선을 순회하면서 각 간선과 x축으로 둘러싸인 사다리꼴의 넓이를 더하면 쉽게 구할 수 있습니다. 여분의 넓이가 상쇄되도록 넓이에 부호를 붙여서 더해야 합니다. 따라서 공식은 다음과 같습니다:

$$A = \sum_{(p,q)\in \text{edges}} \frac{(p_x - q_x) \cdot (p_y + q_y)}{2}$$

코드:

double area(const vector<point>& fig) {
    double res = 0;
    for (unsigned i = 0; i < fig.size(); i++) {
        point p = i ? fig[i - 1] : fig.back();
        point q = fig[i];
        res += (p.x - q.x) * (p.y + q.y);
    }
    return fabs(res) / 2;
}

방법 2¶

점 $O$를 임의로 선택한 뒤, 모든 간선을 순회하면서 각 간선과 점 $O$로 이루어진 삼각형의 방향 있는 넓이를 더할 수 있습니다. 이번에도 넓이의 부호 덕분에 여분의 넓이가 상쇄됩니다.

이 방법은 더 복잡한 경우(예를 들어 일부 변이 직선이 아니라 호인 경우)로 일반화할 수 있으므로 더 좋습니다.