多边形面积计算

要求：计算多边形面积 假设：多边形不存在交叉点 思路：

多边形包括凸多边形和凹多边形。

凸多边形的计算方法一般是将凸多边形分解成多个三角形分别计算面积再求和。如下图的分解方法，从第一点分别向不相邻的点连接，分割为多个n-2个三角形（n为顶点数）。

如果是凹多边形，那么，需要将凹多边形转换为凸多边形后再利用凸多边形的面积减去凹陷的三角形面积后才能计算。这个过程称之为凸化。

首先要解决如何确定哪些顶点是凹点。方法是：如果要检测n点是否为凹点，那么将n点排除在多边形外，将n-1点和n+1点连接，然后检查n点是否落在新的多边形内。如果在，那么n点是个凹点，否则n点是个凸点。

f

a c

e

b d

如上图，我们检测b点是否是凹点，先将a和c点连接，然后检测b点是否

在多边形acdef之内，显然b点不在，那么b点就是凸点。同样检测c点，先将b和d连接，然后检测c点是否在abdef之内，显然c点在，因此c点就是凹点。

每检测到一个凹点，就必须将该凹点排除出多边形，同时必须将该排除点及

其相邻两点记录到裁减三角形数组中。如上例，经过凸化以后，将分解出两组对象，一是最终的凸多边形，二是裁减下来的凹三角形。这里凸多边形就是abdef，凹三角形只有一个，就是bcd。凹三角形可能有多个。 三角形面积的计算

三角形面积的基本计算公式是s = a*h/2。a为一边长，h为对应该边的高。 其它计算公式还有s = a*b*sinα。其中a和b为相邻边，α为相邻边的夹角。 这里考虑使用基本计算公式。因为当前已知条件是三个顶点坐标。因此a比较容易计算。而h的计算可以通过以下公式：

平面内一点P(x0，y0)到一条直线Ax+By+C=0的距离公式：

如果A=0或B=0，上面的距离公式仍然成立。但这是不需要公式就可以求出d = |C|。

根据两点，计算形如Ax+By+C=0形式的方程已有现成的算法：

//直线方程式ax+by+c=0的参数结构 typedef struct _EQUATIONPARA {

double a; //x的参数

double b; //y的参数(为1或0) double c; //常数 }EQUATIONPARA;

//根据两点计算直线方程

void CRouteTools::GetEquationPara(double y2,EQUATIONPARA& outPara) {

if(abs(x1 - x2) < 0.0000001) { outPara.a = 1; outPara.b = 0; outPara.c = -x1; } else

x1,double y1,double x2,double

}

{ }

outPara.b = 1;

outPara.a = - (y1-y2)/ (x1-x2); outPara.c = -(y1+ outPara.a*x1);

根据以上条件，三角形的公式就可以得到了。

算法实现：

任意输入三个以上顶点坐标（要求这些顶点形成的多边形没有相交的边） 将这些顶点转换成屏幕坐标点数组CPointArray

扫描所有顶点，检测每个顶点是凹点还是凸点。扫描方法是检测当前点是否在除去当前点后的多边形区域中，如果在，则是凹点，否则为凸点。如果是凹点，则将该顶点以及相邻的两个顶点记录到以下形式的三角形结构中。 typedef struct _TRIANGLE {

CPoint pt1; CPoint pt2; CPoint pt3; }TRIANGLE;

CArray TriangleAry;

三角形数组定义两个，一个为arConcaveTriangle（凹三角形数组），一个为arProtrudingTriangle（凸三角形数组）。将以上的凹三角形都记录到凹三角形数组中。

对在CPointArray中剩下的点，按照0,1,2、0,2,3、0,3,4、0,4,5的方式组成n-2个三角形，记录到凸三角形数组中。

对于以上的凹凸三角形数组，分别用三角形计算公式计算出总面积，然后将凸三角形总面积减去凹三角形总面积即为最终的结果。

三角形面积计算时，用屏幕坐标计算出垂直线的距离，然后将该距离转换成实际长度，再计算对应边两个端点间的实际距离（注意，这两个端点可以直接用用户输入的顶点中的数据，不要再从屏幕坐标转了，否则会造成更大的误差）。