给定一个有 n 个顶点的多边形的有序坐标。求该多边形的面积。这里的有序是指坐标从第一个顶点到最后一个顶点按顺时针或逆时针排列。示例输入 : X[] {0, 4, 4, 0}, Y[] {0, 0, 4, 4};输出 : 16输入 : X[] {0, 4, 2}, Y[] {0, 0, 4}输出 : 8我们可以使用鞋带公式计算多边形的面积。如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。Area[Tex]\frac{1}{2}\left | \sum_{i1}^{n-1}x_iy_(_i_1_)x_ny1-\sum_{i1}^{n-1}x_(_i_1_)y_i-x_1y_n \right |[/Tex] | 1/2 [ (x1y2 x2y3 ... xn-1yn xny1) - (x2y1 x3y2 ... xnyn-1 x1yn) ] |上述公式是通过对顶点进行叉积来推导多边形中三角形面积的。以下是上述公式的具体实现。示例代码?php// PHP program to evaluate area of// a polygon using shoelace formula// (X[i], Y[i]) are// coordinates of ith point.function polygonArea($X, $Y, $n){// Initialize area$area 0.0;// Calculate value of// shoelace formula$j $n - 1;for ($i 0; $i $n; $i){$area ($X[$j] $X[$i]) *($Y[$j] - $Y[$i]);// j is previous vertex to i$j $i;}// Return absolute valuereturn abs($area / 2.0);}// Driver Code$X array(0, 2, 4);$Y array(1, 3, 7);$n sizeof($X);echo polygonArea($X, $Y, $n);// This code is contributed by ajit?输出2时间复杂度 O(n)辅助空间 O(1)因为没有占用额外的空间。为什么叫鞋带公式这个公式的命名源于我们计算它的方式。例如设输入顶点为(0, 1), (2, 3), and (4, 7).评估过程与系鞋带的过程相匹配。我们将顶点写成如下所示0 12 34 70 1 [写两次]我们评估正项如下0 \ 12 \ 34 \ 70 1即, 0*3 2*7 4*1 18我们评估负项如下0 12 / 34 / 70 / 1即, 0*7 4*3 2*1 14面积 1/2 (18 - 14) 2查看此页以获得更清晰的图像。这是怎么回事我们总是可以将一个多边形分成三角形。面积公式如下取每条边 AB计算顶点位于原点 O 的三角形 ABO 的面积有符号然后取叉积得出平行四边形的面积除以 2。绕多边形旋转时这些面积为正负的三角形会重叠原点和多边形之间的面积会被抵消总和为 0只剩下参考三角形内部的面积。[来源维基百科]为了更好地理解请看下图使用叉积计算三角形面积将多边形划分为更小的三角形来计算面积类似地对于不规则多边形我们可以形成三角形来计算面积相关文章最小成本多边形三角剖分为给定的点集寻找简单闭合路径如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。