浏览量:237

6.4. 多边形的面积

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。

PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry

6.4. 多边形的面积

本节介绍二维和三维多边形面积的计算公式和几何推导方法,针对三维多边形的面积计算,有多种算法,比如三角形分解法、四边形分解法、投影法,本节只介绍三角形分解的方法,并给出相应的计算公式。

6.4.1. 二维空间

问题描述:求二维空间上的多边形\({\rm P} = \{ {V_0},{V_1},...,{V_{n - 1}}\} \)的面积[5, 22],其中,\({{V}_{i}}=({{x}_{i}},{{y}_{i}})\)

二维空间上的多边形\({\rm P}\)的面积通过等式(6.3)计算:

\[{\mathop{\rm Area}\nolimits} ({\rm P}) = \frac{1}{2}\sum\limits_{i = 0}^{n - 1} {{x_i}({y_{i + 1}} - {y_{i - 1}})} \tag{6.3}\]

2015-3-23 17-25-22

图6.26 逆时针方向排序的多边形

接下来,推导下等式(6.3),从几何的角度考虑,设多边形是按照逆时针方向进行排序的,如图6.26所示,\(O\)表示原点,则多边形的面积可以表示为:

\[{\mathop{\rm Area}\nolimits} ({\rm P}) = {\mathop{\rm Area}\nolimits} (O{V_0}{V_1}) + {\mathop{\rm Area}\nolimits} (O{V_1}{V_2}) + \cdots + {\mathop{\rm Area}\nolimits} (O{V_{n - 1}}{V_0}) \tag{6.4}\]

其中,\({\mathop{\rm Area}\nolimits} (\Delta O{V_i}{V_{i + 1}}) = {V_i} \times {V_{i + 1}} = {x_i}{y_{i + 1}} - {x_{i + 1}}{y_i}\)。如果三角形\(\Delta O{V_i}{V_{i + 1}}\)是逆时针顺序的,则有\({\mathop{\rm Area}\nolimits} (\Delta O{V_i}{V_{i + 1}}) \succ 0\);如果是顺时针顺序的,则有\({\mathop{\rm Area}\nolimits} (\Delta O{V_i}{V_{i + 1}}) \prec 0\);如果三点共线,则有\({\mathop{\rm Area}\nolimits} (\Delta O{V_i}{V_{i + 1}}) = 0\)。以图6.26为例,\({\rm P}\)的面积可以理解为多边形\(T=\{O,{{V}_{3}},{{V}_{4}},\cdots ,{{V}_{0}},{{V}_{1}}\}\)的面积减去多边形\(\text{L}=\{O,{{V}_{1}},{{V}_{2}},{{V}_{3}}\}\)的面积,就是灰色的多边形\({\rm P}\)的面积。展开等式(6.4),得到

\[Area(R) = \frac{1}{2}\sum\limits_{i = 0}^{n - 1} {\left( {{x_i}{y_{i + 1}} - {x_{i + 1}}{y_i}} \right)} \tag{6.5}\]

\({{x}_{n}}={{x}_{0}},{{y}_{n}}={{y}_{0}},{{x}_{-1}}={{x}_{n-1}},{{y}_{-1}}={{y}_{n-1}}\),可以继续优化等式(6.5),有

\[\begin{array}{l}{\rm{ }}\frac{1}{2}\sum\limits_{i = 0}^{n - 1} {\left( {{x_i}{y_{i + 1}} - {x_{i + 1}}{y_i}} \right)} \\ = \frac{1}{2}\sum\limits_{i = 0}^{n - 1} {\left[ {{x_i}\left( {{y_{i + 1}} - {y_{i - 1}}} \right) + {x_i}{y_{i - 1}} - {x_{i + 1}}{y_i}} \right]} \\ = \frac{1}{2}\sum\limits_{i = 0}^{n - 1} {{x_i}\left( {{y_{i + 1}} - {y_{i - 1}}} \right)} + \sum\limits_{i = 0}^{n - 1} {\left( {{x_i}{y_{i - 1}} - {x_{i + 1}}{y_i}} \right)} \\ = \frac{1}{2}\sum\limits_{i = 0}^{n - 1} {{x_i}\left( {{y_{i + 1}} - {y_{i - 1}}} \right)} + \left( {{x_0}{y_{ - 1}} - {x_n}{y_{n - 1}}} \right)\\ = \frac{1}{2}\sum\limits_{i = 0}^{n - 1} {{x_i}\left( {{y_{i + 1}} - {y_{i - 1}}} \right)} \end{array}\]

等式(6.5)需要\(2n\)次乘法运算,\(2n\)次加法运算,等式(6.3)需要\(n\)次乘法运算,\(2n-1\)次加法运算,与等式(6.5)相比,减少了\(n\)次乘法计算,效率更高。

上述方法计算出的是多边形\({\rm P}\)的有符号面积。如果多边形\({\rm P}\)是逆时针方向的,则\({\mathop{\rm Area}\nolimits} ({\rm P})\)是正号;如果多边形\({\rm P}\)是顺时针方向的,则\({\mathop{\rm Area}\nolimits} ({\rm P})\)是负号。所以,也可以采用计算出的\({\mathop{\rm Area}\nolimits} ({\rm P})\)的正负号来判定多边形顶点的朝向。判断多边形朝向的另外一种算法是:找到多这形\({\rm P}\)最左边的顶点\(B\)\(B\)的上一个顶点为\(A\)\(B\)的下一个顶点为\(C\),通过判定边\(\overline{AB}\)与边\(\overline{BC}\)的朝向关系来确定多边形的朝向。如果边\(\overline{BC}\)在边\(\overline{AB}\)的左侧,即\( (C-A)\times (B-A)\succ 0\),多边形是逆时针方向;反之,则是顺势针方向。

针对有洞的多边形,如图6.27所示,多边形的面积是外部多边形减去内部多边形,外部多边形的顶点按照逆时针顺序排序,内部多边形的顶点按照顺时针排序,通过等式(6.3)计算出来的就是有洞多边形的面积。

2015-3-23 17-25-38

图6.27 有洞多边形的面积计算

6.4.2. 三维空间

问题描述:求三维空间上的多边形\({\rm P} = \{ {V_0},{V_1},...,{V_{n - 1}}\} \)的面积,其中,\({{V}_{i}}=({{x}_{i}},{{y}_{i}})\),多边形上的顶点在同一个平面上。

Goldman(1991)[23]给出了一个面积的计算公式:

\[{\rm{Area}}(R) = \frac{1}{2}\vec n \cdot \sum\limits_{i = 0}^{n - 1} {\left( {{V_i} \times {V_{i + 1}}} \right)} \tag{6.6}\]

其中,\(\vec{n}\)是平面的法向量,是单位长度,\({{V}_{0}}={{V}_{n}}\)

基于斯托克斯定理,可以证明该等式,这里从几何的角度来考虑这个问题[22]。如图6.28所示,多边形\({\rm P}\)的所有顶点在同一个平面\(\pi \)上,平面的单位长度法向量为\(\vec{n}\),设\(O\)是三维空间上的任意一个点,它与多边形\({\rm P}\)上的任意一条边\(\overline{{{V}_{i}}{{V}_{i+1}}}\)形成一个三角形\(\Delta O{{V}_{i}}{{V}_{i+1}}\)。这就产生了一个以点\(O\)为尖端,以多边形\({\rm P}\)为底的金字塔,那么多边形\({\rm P}\)的面积就是金字塔侧面积在平面上的投影,而侧面是由一个个三角形构成,这就将问题转化为求三角形在平面上的有符号的投影面积。

2015-3-23 17-40-29

图1.28 三维空间下多边形的面积推导

现在考虑任意一个三角形\(\Delta O{{V}_{i}}{{V}_{i+1}}\),如图6.29所示,点\(O\)在平面\(\pi \)上的投影为\(O'\),经过点\(O'\),作一条垂直于边\(\overline{{{V}_{i}}{{V}_{i+1}}}\)的直线,直线与边\(\overline{{{V}_{i}}{{V}_{i+1}}}\)相交于点\(Q\),连接\(OQ\),显然\(\angle O'QO\)就是三角形与平面\(\pi \)的夹角,设夹角为\(\theta \)\(\overline{O'Q}\)\(\Delta O'{V_i}{V_{i + 1}}\)的高,\(\overline{OQ}\)\(\Delta O{{V}_{i}}{{V}_{i+1}}\)的高。三角形的面积向量表示为\(\vec{m}=({{V}_{i}}-O)\times ({{V}_{i+1}}-O)/2\),向量\(\vec{m}\)的长度就是三角形的面积,方向垂直于三角形,易知,向量\(\vec{n}\)\(\vec{m}\)的夹角也是\(\theta \)。因此有

\[{\mathop{\rm Area}\nolimits} (\Delta O'{V_i}{V_{i + 1}}) = \frac{1}{2}\left\| {\overline {O'Q} } \right\| \cdot \left\| {\overline {{V_i}{V_{i + 1}}} } \right\| = \frac{1}{2}\left\| {\overline {OQ} } \right\| \cdot \left\| {\overline {{V_i}{V_{i + 1}}} } \right\| \cdot \cos \theta = \vec n \cdot \vec m \tag{6.7}\]

2015-3-23 17-40-39

图6.29 三角形\(\Delta O{{V}_{i}}{{V}_{i+1}}\)在平面\(\pi \)上的投影

这样计算出来的面积是有符号的,沿着法向量\(\vec{n}\)向下观察\(\Delta O{{V}_{i}}{{V}_{i+1}}\),如果它是逆时针方向的,则计算出来的面积是正数;否则,是负数。计算所有有符号的三角形面积的和,就得到等式(6.6)。算法需要\(6n+3\)次乘法运算,\(4n+2\)次加法运算。

spacer

Leave a reply