计算多角形的面积

计算多边形的面积

题目：输入一个点列，顺次连接成一个封闭多边形，计算多边形的面积

分析：方法一，计算面积可以考虑定积分的形式，定积分有正有负，顺次求和，重复部分相互抵消，最后剩下的总面积的绝对值就是多边形的面积。

从线性积分后的结果可以容易的看出，直线段的积分实际上就是求该直线段与x轴所围成的区域的梯形的面积Int(P1, P2) = Int(k*x + b, P1.x, P2.x) = 0.5 * (P2.x - P1.x) * (P2.y + P1.y), 斜率k = (P1.y - P2.y) / (P1.x - P2.x)，截距b = P1.y - k*P1.x；

算法的复杂度为：O(N)，N为顶点的个数。

struct Point {      float x, y;      Point():x(0.0),y(0.0){}      Point(float _x, float _y):x(_x),y(_y) {}  };  float ComputeTriangleArea(const Point &p1, const Point &p2, const Point &p3) {      return 0.5 * ((p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y));  }  float ComputePolygonAreaTri(const Point points[], int length) {      if (points == NULL || length <= 0) return 0.0;      Point p0(0.0, 0.0);      float area = 0.0;      for (int i = 0; i < length - 1; ++ i) {          area += ComputeTriangleArea(p0, points[i], points[i + 1]);      }      area += ComputeTriangleArea(p0, points[length - 1], points[0]);      return area >= 0.0 ? area : -area;  }  

参考：

[1]http://blog.pfan.cn/rickone/2899.html

[2]http://hi.baidu.com/dayanhn/item/1fe2a2ed8420b80d570f1d68