C++ 求多邊形面積，（通過計算三角形）

題目：輸入一個點列，順次連接配接成一個封閉多邊形，計算多邊形的面積

分析：方法一，計算面積可以考慮定積分的形式，定積分有正有負，順次求和，重複部分互相抵消，最後剩下的總面積的絕對值就是多邊形的面積。

從線性積分後的結果可以容易的看出，直線段的積分實際上就是求該直線段與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
           

{   
    <span style="white-space:pre">	</span>float x, y;   
    };   
    float LinearIntegration(const Point &p1, const Point &p2) 
           

<span style="font-family: 宋體; text-indent: 2em;">{   </span>
           

return 0.5 * (p2.x - p1.x) * (p2.y + p1.y);   
    }   
    float ComputePolygonArea(const Point points[], int length) 
           

{   
    <span style="white-space:pre">	</span>if (points == NULL || length <= 0) return 0.0;   
    <span style="white-space:pre">	</span>float area = 0.0;   
    <span style="white-space:pre">	</span>for (int i = 0; i < length - 1; ++ i) 
           

{   
            area += LinearIntegration(points[i], points[i + 1]);   
   <span style="white-space:pre">	</span>}   
     area += LinearIntegration(points[length - 1], points[0]);   
     return area >= 0.0 ? area : -area;   
    }   
           

方法二，考慮到平面上知道三角形三個頂點的坐标可以運用行列式det直接求解三角形的面積。如P1(x1,y1)，P2(x2,y2)，P3(x3,y3)，則

S(P1, P2, P3) = det[ x1 y1 1; x2 y2 1; x3 y3 1] * 0.5 = [(x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)] * 0.5;

可以在多邊形的平面中任意的找到一個點，與多邊形的每條邊形成有向三角形，并順次求取有向三角形的面積，再加和，因為是有向面積同上述定積分類似，面積有正有負可抵消重複部分，剩下的面積的絕對值即為多邊形的面積。

struct Point 
           

{   
    <span style="white-space:pre">	</span>float x, y;   
    <span style="white-space:pre">	</span>Point() {x = 0.0; y = 0.0;}   
     <span style="white-space:pre">	</span>Point(float _x, float _y) {x = _x; y = _y;}   
    };   
    float ComputeTriangleArea(const Point &p1, const Point &p2, const Point &p3) 
           

{   
    <span style="white-space:pre">	</span>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) 
           

{   
   <span style="white-space:pre">	</span> if (points == NULL || length <= 0) return 0.0;   
   <span style="white-space:pre">	</span> Point p0(0.0, 0.0);   
   <span style="white-space:pre">	</span> float area = 0.0;   
   <span style="white-space:pre">	</span> for (int i = 0; i < length - 1; ++ i) 
           

{   
       <span style="white-space:pre">	</span>     area += ComputeTriangleArea(p0, points[i], points[i + 1]);   
   <span style="white-space:pre">	</span> }   
     area += ComputeTriangleArea(p0, points[length - 1], points[0]);   
     return area >= 0.0 ? area : -area;   
    }   
           

</pre><p></p><p>   搬運工007</p><pre name="code" class="cpp">