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

수학 이야기 2013.08.02 11:38

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

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


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 다크 프로그래머


저작자 표시 비영리 변경 금지
신고
  • BlogIcon 바다야크 2013.08.02 11:48 신고 ADDR 수정/삭제 답글

    수학은 잘 못하지만, 신기하네요. 삼각형하면 높이x밑변/2 뿐이 생각나지 않네요. ^^

  • Furomand 2013.08.02 22:00 신고 ADDR 수정/삭제 답글

    처음 다각형 넓이 구하는 식보고 쑈킹했죠 ㅋ 저렇게 간단하게 표현될수가 하면서

    • BlogIcon 다크pgmr 2013.08.04 00:07 신고 수정/삭제

      ㅎㅎ 식만 간단하게 써 놓고는 진도가 안나가고 있습니다.

    • BlogIcon 다크pgmr 2013.08.10 08:09 신고 수정/삭제

      오늘 드디어 글을 마무리 짓게 되었습니다 ^^

  • 공부중ㅜㅜ 2014.10.27 12:03 신고 ADDR 수정/삭제 답글

    다각형의 변이 겹치는 경우의 넓이 계산은 어떻게 해야할까요??

    Image-Pro 라는 프로그램의 measurement라는 툴이 있습니다
    이 툴에 클릭을 통해 다각형을 그려 넓이를 계산해주는 기능이 있는데, 다각형의 변이 겹치거나 관통하는 경우도 처리를 하여 정확한 넓이를 반환합니다.
    어떤 방법을 통해 빠르게 계산해 내는지 궁금한데 알수가 없네요 ㅠㅠ.. 혹시 조금이라도 이에 관한 방법을 알고계신가요?

    • BlogIcon 다크pgmr 2014.10.28 10:50 신고 수정/삭제

      http://alienryderflex.com/polygon_perimeter/
      에 있는 방법을 참조해 보시기 바랍니다.

    • 공부중ㅜㅜ 2014.10.29 13:36 신고 수정/삭제

      감사합니당!!

  • asas4101 2014.11.15 11:02 신고 ADDR 수정/삭제 답글

    벡터의 외적이 왜 모든 다각형에서 성립되는지 증명은 안되나요?

    • BlogIcon 다크pgmr 2014.11.17 10:55 신고 수정/삭제

      http://www.mathopenref.com/coordpolygonarea2.html
      에 있는 내용을 참고해 보시기 바랍니다.

  • BlogIcon 1nsu 2016.01.30 12:20 신고 ADDR 수정/삭제 답글

    다각형의 넓이에 관한 간단한 내용 정리해서 포스팅하는데 참고했습니다. 괜찮을까요?
    http://1nsunym.github.io/ko/online/2016/01/09/polygon-area/

  • 굿네이버 2016.05.01 18:23 신고 ADDR 수정/삭제 답글

    당신의 설명에 감탄했습니다.
    당신은 천사입니다.

  • 국파피 2016.06.05 20:32 신고 ADDR 수정/삭제 답글

    혹시 각이 없는 경우 구분구적법이나 다른 방법을 이용하여 공간의 면적 및 넓이를 계산 해주는 프로그램은 없나요?

    • BlogIcon 다크pgmr 2016.06.07 16:42 신고 수정/삭제

      그런 소프트웨어가 따로 있는지는 잘 모르겠습니다만 일반적인 도형의 면적을 이미지에서의 픽셀수로 계산하는 것은 충분히 프로그램적으로 구현 가능한 일입니다.

  • 맛챠카스테라 2017.07.21 16:38 신고 ADDR 수정/삭제 답글

    엄청난 글입니다. 좋은 정보 너무 감사합니다



티스토리 툴바