다각형 넓이 (Polygon Area)

정의

다각형 넓이 (Polygon Area) 는 2D 평면 위 단순다각형 (non-self-intersecting polygon) 의 면적을 신발끈 공식 (Shoelace Formula) 으로 O(N) 에 계산하는 알고리즘.

문제 상황과 동기

다각형의 넓이는 기하 문제에서 가장 빈번하게 등장하는 연산.

• Naive: 삼각형 분할 후 각각 넓이 합산. O(N) 이지만 구현이 번거롭고 분할 방식을 결정해야 함.
• Shoelace: 각 변의 기여도를 외적 하나로 계산. O(N) 에 통일된 공식.

핵심 통찰: 다각형의 부호 있는 넓이는 각 변 (i, i+1) 의 외적의 합의 절반. 즉 0.5 * | sum (x_i * y_{i+1} - x_{i+1} * y_i) |.

이 공식은 다각형이 볼록인지 오목인지, 시계/반시계 방향인지 관계없이 항상 성립.

시각화

핵심 아이디어

다각형의 꼭짓점을 P[0], P[1], ..., P[N-1] (반시계 또는 시계). 각 변 P[i] -> P[i+1] 에 대해, 사다리꼴의 부호 있는 넓이 를 더한다.

S = 0
for i in 0..N-1:
    j = (i + 1) % N
    S += P[i].x * P[j].y
    S -= P[j].x * P[i].y
area = abs(S) / 2

이론적 근거: 그린 정리 (Green’s theorem) 의 이산 버전. 각 변의 사다리꼴 넓이가 모두 더해지면 내부는 중첩되고 외부는 상쇄됨.

부호: S > 0 이면 반시계 방향, S < 0 이면 시계 방향.

알고리즘

polygon_area(P[0..N-1]):
    sum = 0
    for i = 0 to N-1:
        j = (i + 1) % N
        sum += P[i].x * P[j].y
        sum -= P[j].x * P[i].y
    return abs(sum) / 2.0

구현

// Polygon area (shoelace), O(N)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
​
struct Point { ll x, y; };
​
double polygon_area(vector<Point>& p) {
  ll sum = 0;
  int n = p.size();
  for (int i = 0; i < n; i++) {
      int j = (i + 1) % n;
      sum += p[i].x * p[j].y;
      sum -= p[j].x * p[i].y;
  }
  return abs(sum) / 2.0;
}
​
int main() {
  vector<Point> poly = {{0,0}, {4,0}, {5,2}, {2,5}, {-1,2}};
  cout << fixed << setprecision(1) << polygon_area(poly) << "\n";
  vector<Point> tri = {{0,0}, {3,0}, {0,4}};
  cout << fixed << setprecision(1) << polygon_area(tri) << "\n";
}

# Shoelace formula, O(N)
def polygon_area(poly):
  n = len(poly)
  s = 0
  for i in range(n):
      j = (i + 1) % n
      s += poly[i][0] * poly[j][1]
      s -= poly[j][0] * poly[i][1]
  return abs(s) / 2.0
​
poly = [(0,0), (4,0), (5,2), (2,5), (-1,2)]
print(f"{polygon_area(poly):.1f}")
tri = [(0,0), (3,0), (0,4)]
print(f"{polygon_area(tri):.1f}")

import java.util.*;
public class Main {
  static double polygonArea(long[][] p) {
      long sum = 0;
      int n = p.length;
      for (int i = 0; i < n; i++) {
          int j = (i + 1) % n;
          sum += p[i][0] * p[j][1];
          sum -= p[j][0] * p[i][1];
      }
      return Math.abs(sum) / 2.0;
  }
​
  public static void main(String[] args) {
      long[][] poly = {{0,0}, {4,0}, {5,2}, {2,5}, {-1,2}};
      System.out.printf("%.1f%n", polygonArea(poly));
      long[][] tri = {{0,0}, {3,0}, {0,4}};
      System.out.printf("%.1f%n", polygonArea(tri));
  }
}

19.0
6.0

복잡도

변형 / 활용

1. 볼록다각형 여부 (방향 일관성)

Shoelace 의 sum 부호로 다각형이 반시계(양수)인지 시계(음수)인지 판별. 모든 연속 세 점의 CCW 가 방향과 일치하는지 확인.

2. 다각형의 무게 중심

면적으로 가중치를 준 꼭짓점 평균으로 centroid 계산 가능.

cx = sum((x_i + x_{i+1}) * (x_i*y_{i+1} - x_{i+1}*y_i)) / (6 * area)
cy = sum((y_i + y_{i+1}) * (x_i*y_{i+1} - x_{i+1}*y_i)) / (6 * area)

3. 오목 다각형에서도 동작

Shoelace 는 내부 영역의 중첩과 상쇄가 자동으로 처리되므로 오목 다각형에서도 올바른 값.

4. 정수 좌표 + long long

좌표가 정수이면 넓이는 .0 또는 .5. 정수 배율 결과가 필요하면 abs(sum) 반환 후 따로 2 로 나누기.

함정

1. 오버플로우

x_i * y_j 가 10^6 * 10^6 = 10^12. N=10^5 면 sum 은 10^17 까지 가능. C++ long long (9e18) 은 OK, int 는 무조건 overflow.

2. 다각형 방향

입력이 시계(cw)인지 반시계(ccw)인지 모를 수 있음. abs(sum) 으로 절대값 처리.

3. 마지막 변

i=N-1 일 때 j=0 으로 돌아오는 것 ((i+1) % N) 이 중요. 열린 폴리라인이 아닌 닫힌 다각형이어야 함.

4. 정수 나눗셈

C++ 에서 abs(sum) / 2 는 정수 나눗셈. 2.0 으로 나누거나 (double) 캐스팅 필요.

BOJ 연습 문제

참고

• CCW (외적의 기초)
• Convex Hull (볼록 껍질에서도 같은 공식)
• Geometry (기하 기본)