欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

计算任意多边形的面积

程序员文章站 2024-03-16 20:08:16
...
“`

计算任意多边形的面积

对于凸多边形,很容易计算,如下图,以多边形的某一点为顶点,将其划分成几个三角形,计算这些三角形的面积,然后加起来即可。已知三角形顶点坐标,三角形面积可以利用向量的叉乘来计算。

计算任意多边形的面积 

 

对于凹多边形,如果还是按照上述方法划分成三角形,如下图,多边形的面积 = S_ABC + S_ACD + S_ADE, 这个面积明显超过多边形的面积。

计算任意多边形的面积

 

我们根据二维向量叉乘求三角形ABC面积时,利用的是

计算任意多边形的面积

这样求出来的面积都是正数,但是向量叉乘是有方向的,即计算任意多边形的面积 是有正负的,如果把上面第三个公式中的绝对值符号去掉,即计算任意多边形的面积 ,那么面积也是有正负的。反应在上面第二个图中,S = S_ABC + S_ACD + S_ADE,如果S_ABC和S_ADE是正的,那么S_ACD是负的,这样加起来刚好就是多边形的面积。对于凸多边形,所有三角形的面积都是同正或者同负。

 

如果我们不以多边形的某一点为顶点来划分三角形而是以任意一点,如下图,这个方法也是成立的:S = S_OAB + S_OBC + S_OCD + S_ODE + S_OEA。计算的时候,当我们取O点为原点时,可以简化计算。                        本文地址

计算任意多边形的面积

当O点为原点时,根据向量的叉积计算公式,各个三角形的面积计算如下:

 

S_OAB = 0.5*(A_x*B_y - A_y*B_x)   【(A_x,A_y)为A点的坐标】

S_OBC = 0.5*(B_x*C_y - B_y*C_x)

S_OCD = 0.5*(C_x*D_y - C_y*D_x)

S_ODE = 0.5*(D_x*E_y - D_y*E_x)

S_OEA = 0.5*(E_x*A_y - E_y*A_x)

 

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct Point2d
{
    double x;
    double y;
    Point2d(double xx, double yy): x(xx), y(yy){}
};
 
//计算任意多边形的面积,顶点按照顺时针或者逆时针方向排列
double ComputePolygonArea(const vector<Point2d> &points)
{
    int point_num = points.size();
    if(point_num < 3)return 0.0;
    double s = 0;
    for(int i = 0; i < point_num; ++i)
        s += points[i].x * points[(i+1)%point_num].y - points[i].y * points[(i+1)%point_num].x;
    return fabs(s/2.0);
}

 

该算法还可以优化一下,对上面的式子合并一下同类项

S = S_OAB + S_OBC + S_OCD + S_ODE + S_OEA =

0.5*(A_y*(E_x-B_x) + B_y*(A_x-C_x) + C_y*(B_x-D_x) + D_y*(C_x-E_x) + E_y*(D_x-A_x))

 

这样减少了乘法的次数,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct Point2d
{
    double x;
    double y;
    Point2d(double xx, double yy): x(xx), y(yy){}
};
 
//计算任意多边形的面积,顶点按照顺时针或者逆时针方向排列
double ComputePolygonArea(const vector<Point2d> &points)
{
    int point_num = points.size();
    if(point_num < 3)return 0.0;
    double s = points[0].y * (points[point_num-1].x - points[1].x);
    for(int i = 1; i < point_num; ++i)
        s += points[i].y * (points[i-1].x - points[(i+1)%point_num].x);
    return fabs(s/2.0);
}

 

【版权声明】转载请注明出处:http://www.cnblogs.com/TenosDoIt/p/4047211.html

2
0
currentDiggType = 0;
« 上一篇:游戏面试题-武器升级
» 下一篇:windows & mac 安装lua
posted @ 2014-10-24 00:04 tenos 阅读(9299) 评论(2) 编辑 收藏

  
#1楼 2016-09-09 12:45 NeXT1995  
double x;
double y;是经纬度,我们算的结果单位是什么?
  
#2楼35067992016/9/9 13:20:03 2016-09-09 13:20 NeXT1995  
如果是墨卡托坐标算了结果是什么单位呢
</div><!--end: forFlow -->
</div>

相关标签: 多边形面积