평면상의 다각형(모서리의 교차가 없는 단순 다각형)의 면적을 구하는 것은 단순하지 않을 것처럼 보이지만 계산식은 무척이나 간단하게 주어진다. 기본적인 아이디어는 다각형에 임의의 점을 찍으면 이 점과 이웃한 두 개의 꼭짓점으로 형성이 되는 삼각형의 합으로 다각형을 분할할 수 있다. 분할된 삼각형의 면적을 구하여 합산하면 다각형의 면적을 구할 수 있다.
세 점 ${\bf P, Q, R}$(이 순서대로 반시계방향으로 배열)이 만드는 삼각형의 면적은
$$\text {삼각형의 면적}= \frac{1}{2} ({\bf R} - {\bf Q}) \times ( {\bf P} - {\bf Q}); \quad (\Rightarrow \text {시계 방향이면 면적이 음수})$$
로 주어지므로, 꼭짓점이 ${\bf P}_0(x_0, y_0), {\bf P}_1(x_1, y_1),....$(반시계 방향)으로 주어지는 $N$각형의 면적은 아래와 같이 주어진다.
$$\begin{align} \text{다각형 면적} &= \sum \text{각 삼각형의 면적} \\ &= \frac{1}{2}\sum ({\bf P}_{i+1}-{\bf Q})\times ({\bf P}_{i}-{\bf Q})\quad \quad ({\bf Q}\text{는 임의의 점})\\ &= \frac{1}{2} \sum\left( {\bf P}_{i+1} \times {\bf P}_{i} - {\bf P}_{i+1}\times {\bf Q} + {\bf P}_{i} \times {\bf Q}\right) \\ &=\frac{1}{2} \sum {\bf P}_{i+1} \times {\bf P}_{i} \\ &= \frac{1}{2}\sum \left( x_{i+1} y_{i} -x_{i}y_{i+1} \right) \end{align}$$
이 결과는 $\bf Q$에 무관하다. 다각형의 꼭짓점이 시계 방향으로 정렬이 된 경우는 면적이 음수로 나온다(윈도우 DC는 위-아래가 역전되어 있으므로 orientation이 반대로 보인다). 그리고 이 공식은 단순 다각형에만 적용이 되고 모서리의 교차가 있는 경우에는 적용이 되지 않는다.
double simple_polygon_area2D(POINT point[], int N) {
double area = 0;
for (int i = 0, j = N - 1; i < N; 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;
}**네이버 블로그 수정 이전;
'Computational Geometry' 카테고리의 다른 글
| 단순 다각형의 Convex hull (0) | 2021.01.24 |
|---|---|
| 단순 다각형의 무게중심 (0) | 2021.01.24 |
| 삼각형 외접원의 Inclusion Test (0) | 2020.12.30 |
| Point in Polygon (2) | 2020.12.14 |
| Catmull-Rom Spline (0) | 2020.12.07 |
