计算任意多边形的面积

简介:

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

image 

 

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

image

 

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

image

这样求出来的面积都是正数,但是向量叉乘是有方向的,即image 是有正负的,如果把上面第三个公式中的绝对值符号去掉,即image ,那么面积也是有正负的。反应在上面第二个图中,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点为原点时,可以简化计算。                        本文地址

image

当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);
}

 






本文转自tenos博客园博客,原文链接:http://www.cnblogs.com/TenosDoIt/p/4047211.html,如需转载请自行联系原作者
目录
相关文章
|
前端开发
饿了么el-dialog自定义内容以及el-dialog自定义样式
饿了么el-dialog自定义内容以及el-dialog自定义样式
947 0
如何关掉Parsed mapper file日志打印
如何关掉Parsed mapper file日志打印
446 1
|
Ubuntu Linux
Linux常用发行版本软件包安装指南
Linux操作系统以其开源、灵活和高度定制的特性而备受欢迎。然而,对于初学者来说,熟悉不同发行版的软件包管理系统可能是一个挑战。本文将介绍在常见的Linux发行版(Ubuntu、CentOS、Alpine)上安装软件包的基本指南,以帮助用户轻松应对软件管理任务。
435 2
Linux常用发行版本软件包安装指南
|
C++ 索引
vscode clangd c++开发常见问题和解决方案
vscode clangd c++开发常见问题和解决方案
3395 0
|
数据可视化 Python
Python中的数据可视化:在数据点上添加标签
Python中的数据可视化:在数据点上添加标签
451 3
|
机器学习/深度学习 算法 Python
Python 使用SMOTE解决数据不平衡问题(最新推荐)
SMOTE是一种强大的过采样技术,可以有效地处理不平衡数据集,提升分类器的性能。通过imbalanced-learn库中的SMOTE实现,我们可以轻松地对少数类样本进行过采样,平衡数据集。在实际应用中,我们可以根据具体数据集的特点和需求,选择合适的过采样方法。
|
JSON 算法 数据可视化
Open3d-Point cloud (点云)
Open3d-Point cloud (点云)
1127 6
|
jenkins Devops 持续交付
jenkins学习笔记之七:jenkins集成LDAP用户认证
jenkins学习笔记之七:jenkins集成LDAP用户认证
|
安全 Linux 网络安全
在Linux中,什么是双因素认证(2FA)?
在Linux中,什么是双因素认证(2FA)?
|
机器学习/深度学习 数据采集 算法
【Python机器学习专栏】支持向量机(SVM)在Python中的实践
【4月更文挑战第30天】SVM是一种高效的监督学习算法,适用于分类和回归,尤其擅长处理高维和非线性问题。通过寻找最大边际超平面来分隔数据,SVM具有高效性、鲁棒性、灵活性和稀疏性等特点。
509 1