다각형 도형의 면적(넓이) 구하기

프로그래밍 등을 할 때 알아두면 유용한 다각형의 면적 구하는 방법입니다.

(오랜만에 수학관련 포스팅을 합니다 ^^)

1. 2차원 평면에서 세 점의 좌표를 알 때 삼각형 면적 구하기

세 점의 좌표를 (x1,y1), (x2,y2), (x3,y3)라 할 때, 세 점을 꼭지점으로 하는 삼각형의 넓이를 일반적으로 구해 보겠습니다.

[헤론의 공식]

물론 가장 간단한 방법은 헤론의 공식을 이용하는 것입니다.

 --- (1)

--- (2)

삼각형의 세 변의 길이를 a, b, c라 할 때 위 식을 이용하면 손쉽게 삼각형 면적을 계산할 수 있습니다.

[벡터의 외적]

그러나 헤론의 공식보다 훨씬 효과적인 방법은 벡터의 외적을 이용하는 것입니다. 여기서 효과적이라는 의미는 프로그래밍 관점에서 연산량이 적다는 의미입니다.

벡터의 외적은 3차원 벡터에서 정의되기 때문에 z = 0으로 생각하고 문제를 적용합니다. 즉, 3차원 공간에서 세 점 (x1,y1,0), (x2,y2,0), (x3,y3,0)이 이루는 삼각형 면적을 구하는 문제로 생각합니다. 두 변을 이루는 벡터를

 --- (3)

로 잡으면 삼각형의 면적은 |a × b|/2 와 같습니다 (두 벡터의 외적의 크기는 두 벡터를 두 변으로 하는 평행사변형의 넓이).

a × b = (0, 0, (x2-x1)(y3-y1)-(x3-x1)(y2-y1))이므로 구하는 삼각형의 면적은 다음과 같습니다.

 --- (4)

훨씬 효과적으로 삼각형의 면적을 계산할 수 있음을 알 수 있습니다.

2. 3차원 공간에서 세 점의 좌표를 알 때 삼각형 면적 구하기

2D의 경우와 마찬가지로 헤론의 공식 또는 벡터의 외적으로 구할 수 있습니다.

세 점을 (x1,y1,z1), (x2,y2,z2), (x3,y3,z3)라 할 때 벡터의 외적을 이용한 결과만 구해보면 다음과 같습니다.

 --- (5)

3차원의 경우에는 식이 좀 복잡하네요..

3. 볼록한 n각형의 면적 구하기

사각형, 오각형, 육각형 등 n각형의 면적은 이들을 삼각형으로 잘게 쪼갠 후 각각 면적을 구해 합치면 됩니다.

그런데 삼각형으로 나눌 때에도 효율적으로 나눠야 합니다. 알고리즘적으로 다각형을 나눌 수 있는 방법은 아래 그림처럼 어느 한 점을 고정하고 이 점이 공통 꼭지점이 되도록 삼각형들을 만들면 될 것입니다.

<그림 1>

만일 P1(x1,y1), P2(x2,y2), ..., Pn(xn,yn)으로 이루어진 n각형이 있다면 이 도형의 면적은 삼각형 P1P2P3, P1P3P4, ..., P1Pn-1Pn의 면적을 구해 모두 합치면 됩니다.

그런데, 만일 도형이 볼록하지 않은 경우에는 어떻게 해야 할까요?

일단은 어떤 도형이 볼록 다각형인지 오목 다각형인지 확인하는 방법부터 알아보겠습니다.

4. 볼록 다각형 / 오목 다각형 판단하기

여기 적는 방법이 가장 효과적인 방법인지는 잘 모르겠지만, 나름 생각한 방법을 적어봅니다.

[방법 1]

어떤 도형이 볼록하려면 임의의 한 변을 잡았을 때, 다른 모든 꼭지점들은 그 변을 확장한 직선을 기준으로 모두 같은 영역에 위치해야 합니다. 예를 들어, 위 그림에서 변 P1P2를 확장한 직선을 생각할 때, P3, P4, ..., Pn은 모두 이 직선의 아래쪽에 존재합니다. 그런데 만일 이 직선 위에 존재하는 꼭지점이 하나라도 존재한다면 이 도형은 오목(concave)하게 됩니다.

이러한 특징을 활용하면 볼록 다각형 여부를 판별할 수 있습니다.

어떤 도형의 방정식 f(x,y) = 0에 의해서 공간이 둘로 나뉜다고 했을 때, 점 (x1,y1), (x2,y2)가 같은 영역에 속할 필요충분 조건은 f(x1,y1)과 f(x2,y2)의 부호가 동일하다 입니다.

따라서 한 변을 지나는 직선의 방정식을 구한 후, 다른 꼭지점들을 이 직선식에 대입했을 때, 모두 같은 부호가 나오는지를 검사하면 됩니다. 이 검사를 모든 변에 대해 수행했을 때 모두 조건이 만족됐다면 이 도형은 볼록 다각형입니다.

변 P1P2의 경우만 예를 들어 보겠습니다.

P1(x1,y1), P2(x2,y2)를 지나는 직선의 방정식은 f(x,y) = (x2-x1)(y-y1)-(y2-y1)(x-x1) = 0이므로 변 P1P2의 경우에는 f(x3,y3), f(x4,y4), ..., f(xn,yn)이 모두 같은 부호인지 체크해 보면 됩니다.

☞ 참고로, 두 점 (x1,y1), (x2,y2)과 도형의 방정식 f(x,y) = 0 이 있을 때, 두 점이 같은 영역에 있을 조건은 f(x1,y1)f(x2,y2)>0, 서로 다른 영역에 있을 조건은 f(x1,y1)f(x2,y2)<0, 도형위에 있을 조건은 f(x1,y1)=0, f(x2,y2)=0 입니다. 이러한 원리를 이용하면 영상처리 등을 할 때 매우 유용하게 활용할 수 있습니다. 예를 들어, 3차원 공간에서 어떤 점 p가 평면 f에 의해 시야에서 가려졌는지 여부를 판단하려면 시점(카메라 위치) v에 대해 f(p)f(v)<0인지를 검사하면 됩니다.

[방법 2]

그런데 생각해 보니 방법 1처럼 우회적인 방법이 아니라 직접적으로 오목/볼록을 판단할 수 있는 방법도 있겠네요.

즉, 각 꼭지점에서의 내각의 크기를 조사하여 180도보다 작으면 볼록, 180도 보다 크면 그 점에서 오목이라고 판별하는 것입니다. 이렇게 하면 각각의 꼭지점이 볼록인지 오목인지 여부도 같이 판별할 수 있는 장점도 있습니다.

다각형의 한 내각의 크기는 이웃한 두 변의 사잇각을 구해야 합니다. 예를 들어, 위 그림에서 점 P2가 오목인지 볼록인지 알기 위해서는 두 벡터 P2P1 = (x1-x2, y1-y2), P2P3 = (x3-x2, y3-y2)의 사잇각을 구해야 합니다.

두 벡터의 사잇각은 벡터의 내적을 이용하여 구합니다. 두 벡터 a = (x1, y1), b = (x2, y2)가 이루는 각을 θ라 하면 a·b = |a||b|cosθ 이므로

 --- (6)

그런데 벡터의 내적은 a·b = b·a로 순서에 관계없기 때문에 아래 그림과 같은 두 경우를 구분하지 못하는 문제가 있습니다. 즉, 식 (6)을 만족하는  θ가 0 ~ 2π 범위에서 2개 있는데 이중 어느 것이 a에서 b로의 각인지 내적만으로는 알 수가 없습니다.

<그림 2>

방향을 알아내기 위해 제가 생각해낸 방법은 벡터의 외적을 이용하는 것입니다.

만일 a×b>0 라면 위 그림 왼쪽 경우처럼 내각이 θ<π 인 볼록한 경우이고, a×b<0 라면 오른쪽 경우처럼 내각이 θ>π  인 오목한 경우입니다. 만일 a×b = 0 이라면 θ = 0이거나 θ = π인 경우입니다.

방법을 생각하다 보니.. 만일 내각의 값을 구할 필요가 없고 오직 오목/볼록 여부만 판단하고자 한다면 벡터의 외적만 사용해도 되겠네요. 단, 벡터 외적을 적용하기 위해서는 두 벡터를 a = (x1,y1,0), b = (x2,y2,0)과 같이 3차원으로 확장해서 사용해야 합니다.

벡터의 외적은 정말 활용도가 무궁무진하군요 ^^.

5. 오목한 n각형의 면적 구하기

만일 오목점이 1개인 경우에는 아래 그림처럼 오목점을 중심으로 볼록 다각형의 경우와 동일하게 삼각형으로 나누어 면적을 구하면 됩니다.

<그림 3>

그런데, 아래 그림처럼 오목점이 여러개인 경우에는 위 방법만으로는 면적을 구할 수가 없습니다.

<그림 4>

이 경우에는 삼각형에 따라서 어떤 삼각형은 면적을 더해줘야 하고 어떤 삼각형은 면적을 빼줘야 합니다. 예를 들어, 위 그림의 다각형 면적은 S = -P1P2P3 + P1P3P4 + ... + P1Pn-1Pn 과 같이 구할 수 있습니다.

이 문제를 좀더 일반화해서 P1, P2, ..., Pn을 꼭지점으로 하는 n각형의 면적을 구하는 식을 다음과 같이 잡아보겠습니다.

 --- (7)

식 (7)에서 sign()은 +1 또는 -1의 값을 갖는 부호함수이고, area는 삼각형의 면적을 나타내는 함수입니다.

-- (이하 8.10일 추가된 내용)

관건은 삼각형의 부호를 결정하는 것인데, 그건 삼각형의 세 점을 순회하는 방향을 이용합니다.

즉, 점 P1PiPi+1이 시계방향인지 반시계 반향인지에 따라서 부호를 결정합니다. 어느 방향을 +, -로 해도 관계는 없으며 식 (7)에서와 같이 최종 결과에 절대값을 취하면 됩니다.

여기서는 예를 들어, 시계 방향을 +, 반시계 방향을 -라 잡고 위 <그림 4>의 삼각형 면적을 구해보겠습니다.

먼저, 삼각형 P1P2P3는 반시계 방향이므로 삼각형 면적을 뺍니다. 다음으로 삼각형 P1P3P4는 시계방향이므로 면적을 더합니다. 그 다음 P1P4P5, ..., P1Pn-1Pn은 모두 시계방향이므로 면적을 더합니다. 그러면 원래 다각형 면적이 나옴을 확인할 수 있습니다.

그런데, 위 식 (7)은 어떤 점을 시작점으로 잡아도 항상 다각형의 면적이 나옴을 확인할 수 있습니다. 예를 들어, P3를 시작점으로 잡고, 삼각형 P3P4P5, P3P5P6, ..., P3PnP1, P3PnP2까지 면적을 삼각형 방향에 따라 더하고 빼보면 다각형의 면적이 나옴을 알 수 있습니다.

6. 일반적인 n각형의 면적 구하기 (오목/볼록 관계없이 적용)

사실 위 식 (7)은 오목 다각형 뿐만 아니라 볼록 다각형에도 성립합니다. 즉, 오목/볼록 여부에 관계없이 다각형의 면적을 일반적으로 구할 수 있는 식입니다.

그런데, sign(△P1PiPi+1)을 결정하기 위해 △P1PiPi+1이 시계방향인지 반시계반향인지 알아내는게 문제입니다.

그런데 이 문제는 벡터의 외적을 이용하면 깔끔하게 해결됩니다. 벡터의 외적은 방향에 따라 부호가 바뀌기 때문입니다. 따라서, 앞서 식 (4)의 삼각형 면적 구하는 식에서 절대값을 없앤 식을 사용하면 됩니다. 즉, 삼각형의 부호와 면적을 따로 구할 필요없이 식 (4)의 벡터의 외적값으로 부호와 면적을 한꺼번에 구하면 됩니다.

즉, P1(x1, y1), P2(x2, y2), ..., Pn(xn, yn)을 꼭지점으로 하는 n각형의 면적을  오목/볼록 관계없이 일반적으로 다음과 같이 구할 수 있습니다.

 --- (8)

7. n각형의 면적 구하는 또 다른 방법

인터넷을 검색해 보니 약간 다른 수식으로 n각형의 면적을 일반적으로 구하는 방법이 있어서 같이 소개합니다 (오목/볼록 모두 적용)

http://www.mathopenref.com/coordpolygonarea2.html에 보면 (x1,y1), ..., (xn,yn)으로 이루어진 n각형의 면적 구하는 식이 다음과 같이 나와 있습니다.

 --- (9)

단, 여기서 i = n일 때의 xn+1은 xn에 연결된 다음의 점 즉, x1을 의미합니다. 마찬가지로 yn+1은 y1을 의미합니다. 이 사이트에는 왜 이 식이 면적이 되는지도 직관적으로 잘 설명되어 있습니다.

계산 결과는 같습니다만, 제가 유도한 식 (8)보다는 식 (9)가 훨씬 간결하네요.. ^^;

마지막으로, 머리속에 기억하기 좋은 다른 수식 표현으로는 다음과 같은 것도 있습니다 (출처 http://mathworld.wolfram.com/PolygonArea.html)

 --- (10)

식 (10)은 학창시절에 어디선가 한번은 봤던 기억이 납니다. 즉, x좌표와 y좌표들을 순서대로 쭉 나열하고 맨 마지막에 x1, y1을 덧붙입니다. 그리고 나서 오른쪽 대각선 방향으로 좌표들을 곱한 값들에서 왼쪽 대각선 방향으로 곱한 값들을 빼준 후 1/2을 하면 면적이 나온다는... 

물론 식 (10)도 오목/볼록 모든 경우에 성립합니다.

한가지 주의사항은 식 (8), (9), (10) 모두 다각형의 변들이 서로 교차하는 경우에는 성립하지 않습니다.

☞ 꼭 이 글에 있는 문제 뿐만 아니라 풀이 과정에서 사용된 여러 수학적 원리를 이해하면 여러모로 쓸모가 많을 것으로 생각합니다. 예를 들어, 볼록 다각형을 판단하는 방법은 영상 homography 행렬이 유효한 행렬인지 여부를 판단할 때 사용할 수 있습니다.

by 다크 프로그래머