如何计算不规则多边形的面积

Question

包括 各种形状的多边形，请给出具体算法，有现成的程序也好：

输入：给定多边形的路径：（x0,x1）,(x2,x2),...,(xN,yN)；这些边可能交叉

输出：面积
请注意，任意多边形，包括凹多边形

Answer 1

做法：（先说不交叉的情况）
1.根据三角形的3个顶点的坐标，可以算出三角形的面积。这个公式自己可以推论出来
2.算法：
struct Points
{
int x,y;
}Point;

Point ar[N]; //

for(i=0;i<N;i++)
{
ar[i].x=x0; //x0,y0,可由外部输入，或其他到入
ar[i].y=y0;
}
然后利用将多边行分成N个三角形来处理，总面积=每个小三角形之和
Point temp;
temp.x=ar[1].x;
temp.y=ar[1].y
M=N-3;
Point A,B,C;
for(j=0;j<M;j++)//假设可以分成M个三角形
{
for(k=0;k<3;k++)
{
计算三角形的面积
}
}
最后加起来

至于交叉的情况，比较复杂，算法可根据上面的思路来思考