任意多边形面积计算
之前，應(yīng)朋友所托，完成個四邊形面積計算程序，于是不由自主考慮來個擴展，解決任意多邊形面積的計算。
?????? 一開始想到了某定點的三角形剖分，但遇到凹凸多邊形引發(fā)的多種情況，過于復(fù)雜，放棄。
?????? 后來想到用圖形學(xué)中填充算法中的掃描線方法，切分成梯形與三角形，將交點存入活性邊表后再計算面積，感覺也較復(fù)雜，放棄。
?????? 再然后，找到個計算幾何大神O’Rourke在1998年公開的成果。
*（書名：Computational Geometry in C，第二版P20）*
1-原理介紹
?????? 上書中給出定理：
任意多邊形的面積可由任意一點與多邊形上依次兩點連線構(gòu)成的三角形矢量面積求和得出。
?????? 矢量面積=三角形兩邊矢量的叉乘。
?????? 如下圖：
?
按定理，多邊形面積由P點與A-G的各頂點連接所構(gòu)成的三角形矢量面積構(gòu)成，假定多邊形頂點坐標順序為A-G，逆時針為正方向，則有如下結(jié)論：
PAB,PBC,PCD均為順時針，面積為負；
PDE，PEF，PFG，PGA均未逆時針，面積為正；
但無論正負，均可通過P點與頂點連線的矢量叉乘完成，叉乘結(jié)果中已包含面積的正負。
?
2-程序設(shè)計
采用C++的vector（動態(tài)數(shù)組）存儲頂點坐標。
為方便計算，直接將P點定為原點（0,0），則多邊形頂點xy坐標即為向量在xy上分量。
循環(huán)計算多邊形頂點坐標每一點與下一點之間的線段，及這兩點與P連線的矢量所圍成的三角形面積。
計算面積的函數(shù)代碼如下：
iArea=iArea+(vecPoly[iCycle].x*vecPoly[(iCycle+1) % iCount].y-vecPoly[(iCycle+1) % iCount].x*vecPoly[iCycle].y); int intAreaCalc(vector<myPoint> &vecPoly) {int iCycle,iCount,iArea;iCycle=0;iArea=0;iCount=vecPoly.size();for(iCycle=0;iCycle<iCount;iCycle++){ iArea=iArea+(vecPoly[iCycle].x*vecPoly[(iCycle+1) % iCount].y-vecPoly[(iCycle+1) % iCount].x*vecPoly[iCycle].y);}return abs(0.5*iArea); }注意，要注意的是最后一個頂點，要與第一個頂點練成三角形，可將循環(huán)變量對頂點總數(shù)求同余，則循環(huán)過程中的最后一點+1后，自然會成為第一個頂點，上述代碼中的“% iCount”即為解決此問題。
?
完整程序，請下載工程文件。
?http://files.cnblogs.com/vbspine/sdkPoly.rar
Ps：上述程序在Win7x64，VS2008環(huán)境下編譯通過。
轉(zhuǎn)載：http://www.cnblogs.com/vbspine/archive/2013/03/28/2987818.html
?方法：轉(zhuǎn)自紅黑聯(lián)盟：http://www.2cto.com/kf/201210/162799.html
題目：輸入一個點列，順次連接成一個封閉多邊形，計算多邊形的面積
分析：方法一，計算面積可以考慮定積分的形式，定積分有正有負，順次求和，重復(fù)部分相互抵消，最后剩下的總面積的絕對值就是多邊形的面積。
從線性積分后的結(jié)果可以容易的看出，直線段的積分實際上就是求該直線段與x軸所圍成的區(qū)域的梯形的面積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；
算法的復(fù)雜度為：O(N)，N為頂點的個數(shù)。
[cpp code]
struct Point {
float x, y;
};
float LinearIntegration(const Point &p1, const Point &p2) {
return 0.5 * (p2.x - p1.x) * (p2.y + p1.y);
}
float ComputePolygonArea(const Point points[], int N) {
if (points == NULL || N <= 0) return 0.0;
float area = 0.0;
for (int i = 0; i < N - 1; ++ i) {
area += LinearIntegration(points[i], points[i + 1]);
}
area += LinearIntegration(points[N - 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;
可以在多邊形的平面中任意的找到一個點，與多邊形的每條邊形成有向三角形，并順次求取有向三角形的面積，再加和，因為是有向面積同上述定積分類似，面積有正有負可抵消重復(fù)部分，剩下的面積的絕對值即為多邊形的面積。
[cpp code]
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 N) {
if (points == NULL || N <= 0) return 0.0;
Point p0(0.0, 0.0);
float area = 0.0;
for (int i = 0; i < N - 1; ++ i) {
area += ComputeTriangleArea(p0, points[i], points[i + 1]);
}
area += ComputeTriangleArea(p0, points[N - 1], points[0]);
return area >= 0.0 ? area?: -area;
}
?
實例：
[cpp test code]
#include
using namespace std;
?
struct Point
{??
????float x, y;??
};??
float LinearIntegration(const Point &p1, const Point &p2)
{??
????return 0.5 * (p2.x - p1.x) * (p2.y + p1.y);??
}??
float ComputePolygonArea(const Point points[], int length)
{??
????if (points == NULL || length <= 0) return 0.0;??
????float area = 0.0;??
????for (int i = 0; i < length - 1; ++ i)
????{??
????????area += LinearIntegration(points[i], points[i + 1]);??
????}??
????area += LinearIntegration(points[length - 1], points[0]);??
????return area >= 0.0 ? area : -area;??
}??
?
int main()
{
????int n;
????while(cin>>n && n!=0)
????{
???????Point a[n];
???????for(int i=0; i
???????????cin>>a[i].x>>a[i].y;
???????float ans = ComputePolygonArea(a,n);
???????cout<<ans<<endl;
????}
????return 0;
?
}
題目：http://acm.whu.edu.cn/learn/problem/detail?problem_id=1402
DescriptionMr. Tenant is going to buy a new house. In fact, he is going to buy a piece of land and build his new house on it. In order to decide which piece of land to buy, Mr. Tenant needs a program which will give a score to each piece. Each candidate piece of land is a polygonal shape (not necessarily convex), and Mr.?Tenant wonders what the best score is. Among possible scores, he considered the number of vertices, sum of angles, minimum number of required guards, and so forth. Finally, Mr. Tenant decided that the best score for a piece of land would simply be its area. Your task is to write the desired scoring program.
Input The input file consists of multiple pieces of land. Each piece is a simple polygon (that is, a polygon which does not intersect itself). A polygon description starts with a positive integer number k, followed by k vertices, where each vertex consists of two coordinates (floating-point numbers): x and y. Naturally, the last vertex is connected by an edge to the first vertex. Note that each polygon can be ordered either clockwise or counterclockwise. The input ends with a "0" (the number zero). Output For each piece of land, the output should consist of exactly one line containing the score of that piece, rounded to the nearest integer number. (Halves should be rounded up, but Mr. Tenant never faced such cases.) Hint: The scoring program has to handle well degenerate cases, such as, polygons with only one or two vertices. Sample Input 1 123.45 67.8903 0.001 0 1.999 0 0 2
5 10 10 10 12 11 11 12 12 12.0 10.0
0
Sample Output
?
02
3
轉(zhuǎn)載：http://blog.sina.com.cn/s/blog_a2ae2da90101ofk7.html
總結(jié)
- 上一篇： Java parallel Bucket
- 下一篇： 牛客网：全排列