ConvexPolygonArea 凸多边形面积

问题

求凸多边形面积。

三角形面积

向量$\vec{v_{1}}$和$\vec{v_{2}}$的叉积的值恰好等于由$\vec{v_{1}}$、$\vec{v_{2}}$组成的平行四边形的面积，组成的三角形的面积的$2$倍。

ConvexPolygonArea1.png

因此有

$$Area_{3} = \frac {\vec{v_1} \times \vec{v_2}} {2}$$

计算三角形面积的时间复杂度为$O(1)$。

多边形面积

二维坐标系上的$n$多边形有$n$个顶点，随意选取一个顶点$p$。$p$与多边形上其他每条边的两个端点组成一个三角形（共$n - 2$个三角形），像这样顶点$p$与所有边分别组成的所有三角形的面积之和，即为该多边形的面积。注意到叉积的值可能为负数，最终的面积取绝对值即可。如图所示：

ConvexPolygonArea2.png

因此有

$$Area_{n} = \frac {\sum_{i=1}^{n-1} \vec{v_i} \times \vec{v_{i+1}}} {2}$$

计算多边形面积的时间复杂度为$O(n)$。

源码

ConvexPolygonArea.h

ConvexPolygonArea.cpp

测试

ConvexPolygonAreaTest.cpp