C++ 给定 n 个有序顶点的多边形的面积(Area of a polygon with given n ordered vertices)

给定一个有 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_{i=1}^{n-1}x_iy_(_i+_1_)+x_ny1-\sum_{i=1}^{n-1}x_(_i+_1_)y_i-x_1y_n \right |[/Tex]

= | 1/2 [ (x1y2 + x2y3 + ... + xn-1yn + xny1) - (x2y1 + x3y2 + ... + xnyn-1 + x1yn) ] |

上述公式是通过对顶点进行叉积来推导多边形中三角形面积的。 
以下是上述公式的具体实现。 

示例代码：

// C++ program to evaluate area of a polygon using
// shoelace formula
#include <bits/stdc++.h>
using namespace std;

// (X[i], Y[i]) are coordinates of i'th point.
double polygonArea(double X[], double Y[], int n)
{
    // Initialize area
    double area = 0.0;

    // Calculate value of shoelace formula
    int j = n - 1;
    for (int i = 0; i < n; i++)
    {
        area += (X[j] + X[i]) * (Y[j] - Y[i]);
        j = i;  // j is previous vertex to i
    }

    // Return absolute value
    return abs(area / 2.0);
}

// Driver program to test above function
int main()
{
    double X[] = {0, 2, 4};
    double Y[] = {1, 3, 7};

    int n = sizeof(X)/sizeof(X[0]);

    cout << polygonArea(X, Y, n);
}

输出 ： 

2

时间复杂度： O(n) 

辅助空间： O(1)，因为没有占用额外的空间。

为什么叫鞋带公式？ 

这个公式的命名源于我们计算它的方式。 

例如： 

设输入顶点为
 (0, 1), (2, 3), and (4, 7). 

评估过程与系鞋带的过程相匹配。

我们将顶点写成如下所示
  0    1
  2    3
  4    7
  0    1  [写两次]

我们评估正项如下
  0  \  1
  2  \  3
  4  \  7
  0     1  
即, 0*3 + 2*7 + 4*1 = 18 

我们评估负项如下
  0     1
  2  /  3
  4  /  7
  0  /  1  
即, 0*7 + 4*3 + 2*1 = 14

面积 = 1/2 (18 - 14) = 2 

查看此页以获得更清晰的图像。

这是怎么回事？ 
我们总是可以将一个多边形分成三角形。面积公式如下：取每条边 AB，计算顶点位于原点 O 的三角形 ABO 的面积（有符号），然后取叉积（得出平行四边形的面积）除以 2。绕多边形旋转时，这些面积为正负的三角形会重叠，原点和多边形之间的面积会被抵消，总和为 0，只剩下参考三角形内部的面积。[来源：维基百科] 

为了更好地理解，请看下图：

使用叉积计算三角形面积

将多边形划分为更小的三角形来计算面积

类似地，对于不规则多边形，我们可以形成三角形来计算面积

相关文章： 
最小成本多边形三角剖分， 
为给定的点集寻找简单闭合路径

如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。