C++ 计算给定 n 个有序顶点多边形的面积
给定一个有 n 个顶点的多边形，其顶点坐标按顺时针或逆时针顺序排列。本例介绍如何计算该多边形的面积。
示例
输入：X[] = {0, 4, 4, 0}, Y[] = {0, 0, 4, 4} 输出：16
输入：X[] = {0, 4, 2}, Y[] = {0, 0, 4} 输出：8
我们可以使用鞋带公式（Shoelace Formula）计算多边形的面积。
面积计算公式如下： Area = 1/2 * | sum(xi*y(i+1)) - sum(x(i+1)*yi) |
上述公式是通过对顶点进行叉积来推导多边形中三角形面积的。以下是具体实现。
示例代码
// 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 即：03 + 27 + 4*1 = 18
评估负项如下： 0 1 2 / 3 4 / 7 0 / 1 即：07 + 43 + 2*1 = 14
面积 = 1/2 * (18 - 14) = 2
查看 维基百科 以获得更清晰的图像。
原理说明
我们总是可以将一个多边形分成三角形。面积公式如下：取每条边 AB，计算顶点位于原点 O 的三角形 ABO 的面积（有符号），然后取叉积（得出平行四边形的面积）除以 2。绕多边形旋转时，这些面积为正负的三角形会重叠，原点和多边形之间的面积会被抵消，总和为 0，只剩下参考三角形内部的面积。
为了更好地理解，请看下图：
