当前位置:   article > 正文

求多边形面积_凹多边形面积公式

凹多边形面积公式

计算任意多边形的面积

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

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

}


求多边形的面积

给定多边形的顶点坐标(有序),让你来求这个多边形的面积,你会怎么做?
我们知道,任意多边形都可以分割为N个三角形,所以,如果以这为突破点,那么我们第一步就是把给定的多边形,分割为数个三角形,分别求面积,最后累加就可以了,把多边形分割为三角形的方式多种多样,在这里,我们按照如下图的方法分割:

图1

 

S点作为起始点(点1),a->e依次作为点2,3……。
一个三角形的面积是怎样的呢?
根据线性代数的知识,我们有如下的三角形面积公式,称之为有向面积(signed area):

将这个行列式以第三列展开可以得到:

这就是以点1、2、3构成的三角形的有向面积(点如果是顺时针给出,有向面积为负,逆时针给出,有向面积为正),那么继续我们的工作,通过三角形的面积公式,来得到多边形的面积公式:
对于图1而言,多边形的面积就是:
S(1->6)=S(1,2,3)+S(1,3,4)+S(1,4,5)+S(1,5,6)
这里我们不免有些疑问,第一,图1所给出的是凸多边形,那这种算法对于非凸多边形是否同样适用呢?比如下面这个最简单的凸多边形的图形:

图2

用刚才的划分方法的话,就会出现一个诡异的问题,那就是有一个三角形出现在了图形的外面,而另外一个又超出了多边形的范围(划分为了Sab,Sbc两个图形),那么这样再用刚才的公式求面积,结果还是正确的么?
S(1->4)=S(1,2,3)+S(1,3,4)
先公布结论,这个式子是正确的,等等,为什么?还记得刚才我提到了那个“有向面积”的概念么?忘了的话,请回头看看加重了的字。
请注意从图中看,Sab点为顺时针排列,Sbc点为逆时针排列,面积从数值上就是从Sab这个超过范围的大三角形中去掉Sbc这个小三角形,最后的结果神奇的就是多边形Sabc的面积,那么这个结论能否推广到任意多边形呢?

图3

在这里不做证明,下面给出的公式,就是任意多边形的面积公式:

  1. #include<cstdio>
  2. #include<iostream>
  3. using namespace std;
  4. struct P{
  5. int x;
  6. int y;
  7. }p[105];
  8. double area(int a)
  9. {
  10. int b = a-1;
  11. return (p[b].x*p[a].y-p[a].x*p[b].y)-(p[0].x*p[a].y-p[a].x*p[0].y)+(p[0].x*p[b].y-p[b].x*p[0].y);
  12. } //这就是数量积的最简形式
  13. int main() //一个多边形最少可以分成n-2个三角形
  14. {
  15. int n;
  16. while(cin >> n){
  17. if(n==0) break;
  18. for(int i=0;i<n;i++)
  19. cin >> p[i].x >> p[i].y;
  20. double sum = 0;
  21. for(int i=2;i<n;i++){
  22. sum +=area(i)/2.0; //从第三个点开始求面积
  23. }
  24. printf("%0.1ld",sum);
  25. }
  26. return 0;
  27. }

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Guff_9hys/article/detail/833759
推荐阅读
相关标签
  

闽ICP备14008679号