devbox
凡人多烦事01
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++ 计算多边形的面积，计算IOU_c++计算多边形面积

作者：凡人多烦事01 | 2024-02-19 10:04:25

赞

踩

c++计算多边形面积

 

  1. //求任意多边形的面积
  2. /*语法：result = polygonarea(vector<Point>&polygon, int N);
  3. 参数：
  4. polygon：多变形顶点数组
  5. N：多边形顶点数目
  6. 返回值：多边形面积
  7. 注意：
  8. 支持任意多边形，凹、凸皆可
  9. 多边形顶点输入时按顺时针顺序排列
  11. */
  12. #include <iostream>
  13. #include <vector>
  14. using namespace std;
  15. typedef struct  Point{
  16.     double x, y;
  17.     Point(){}
  18. } Point;
  19. double polygonarea(vector<Point>&polygon, int N)
  20. {
  21.     int i, j;
  22.     double area = 0;
  23.     for (i = 0; i<N; i++) {
  24.         j = (i + 1) % N;
  25.         area += polygon[i].x * polygon[j].y;
  26.         area -= polygon[i].y * polygon[j].x;
  27.     }
  28.     area /= 2;
  29.     return(area < 0 ? -area : area);
  30. }
  31.  
  32. //测试函数
  33. int main(){
  34.  
  35.     vector<Point> polygon;
  36.     int n;
  37.     cin >> n;
  38.     polygon.resize(n);
  39.     int i = 0;
  40.     while (n--){
  41.         double x, y;
  42.         cin >> x >> y;
  43.         polygon[i].x = x;
  44.         polygon[i].y = y;
  45.         ++i;
  46.     }
  47.     cout << "此多边形的面积为" << polygonarea(polygon, polygon.size()) << endl;
  48.  
  49.  
  50.     return 0;
  51. }
  52.  
  53.

参考：C++实现——任意多边形的面积

参考：C++实现多边形面积的计算

参考：C++ 描述任意多边形的类及计算其面积和周长

 

计算IOU代码稍后补充。

计算IOU最初只计算正矩形的IOU，当矩形有角度或者任意四边形的IOU计算就比较困难。一般见到的计算IOU都是python直接调用封装好的库。如下，下面代码从shapely中导出Polygon库，其实可以直接导入Polygon库。

看到一篇clipper和Polygon的文章：python多边形裁剪库效果对比

背景：在进行目标检测时，常常会用到交并比的概念(IoU(Intersection over Union))

                                                             IoU=\frac{Area\, of\, Overlap}{Area\, of\, Union}

一般来说，这个IoU ＞ 0.5 就可以被认为是一个不错的结果

1.规则矩形框的IoU计算

有些目标检测中，预测的边界框为规则的矩形，则只需要知道矩形的左上角和右下角的坐标信息，就可以得到矩形框所有想要的信息。对于这种情况，IoU的python实现如下（python3.5）

  1. def IoU(box1, box2):
  2.     '''
  3.     计算两个矩形框的交并比
  4.     :param box1: list,第一个矩形框的左上角和右下角坐标
  5.     :param box2: list,第二个矩形框的左上角和右下角坐标
  6.     :return: 两个矩形框的交并比iou
  7.     '''
  8.     x1 = max(box1[0], box2[0])   # 交集左上角x
  9.     x2 = min(box1[2], box2[2])   # 交集右下角x
  10.     y1 = max(box1[1], box2[1])   # 交集左上角y
  11.     y2 = min(box1[3], box2[3])   # 交集右下角y
  12.  
  13.     overlap = max(0., x2-x1) * max(0., y2-y1)
  14.     union = (box1[2]-box1[0]) * (box1[3]-box1[1]) \
  15.             + (box2[2]-box2[0]) * (box2[3]-box2[1]) \
  16.             - overlap
  17.  
  18.     return overlap/union
  19. if __name__ == '__main__':
  20.     # box = [左上角x1,左上角y1,右下角x2,右下角y2]
  21.     box1 = [10, 0, 15, 10]
  22.     box2 = [12, 5, 20, 15]
  23.     iou = IoU(box1, box2)

2. 非矩形框IoU计算

在有些目标检测中，检测框并不是规则的矩形框，例如自然场景下的文本检测，有些呈现平行四边形，梯形等情况，这时计算IoU时，就比较复杂一些。这时可以借助于python的一些库实现多边形的面积计算

  1. import shapely
  2. import numpy as np
  3. from shapely.geometry import Polygon, MultiPoint  # 多边形
  4.  
  5. def bbox_iou_eval(box1, box2):
  6.     '''
  7.     利用python的库函数实现非矩形的IoU计算
  8.     :param box1: list,检测框的四个坐标[x1,y1,x2,y2,x3,y3,x4,y4]
  9.     :param box2: lsit,检测框的四个坐标[x1,y1,x2,y2,x3,y3,x4,y4]
  10.     :return: IoU
  11.     '''
  12.     box1 = np.array(box1).reshape(4, 2)  # 四边形二维坐标表示
  13.     # python四边形对象，会自动计算四个点，并将四个点重新排列成
  14.     # 左上，左下，右下，右上，左上（没错左上排了两遍）
  15.     poly1 = Polygon(box1).convex_hull
  16.     box2 = np.array(box2).reshape(4, 2)
  17.     poly2 = Polygon(box2).convex_hull
  18.  
  19.     if not poly1.intersects(poly2):  # 如果两四边形不相交
  20.         iou = 0
  21.     else:
  22.         try:
  23.             inter_area = poly1.intersection(poly2).area  # 相交面积
  24.             iou = float(inter_area) / (poly1.area + poly2.area - inter_area)
  25.         except shapely.geos.TopologicalError:
  26.             print('shapely.geos.TopologicalError occured, iou set to 0')
  27.             iou = 0
  28.  
  29.     return iou
  30.  
  31. if __name__ == '__main__':
  32.     # box = [四个点的坐标，顺序无所谓]
  33.     box3 = [10, 0, 15, 0, 15, 10, 10, 10]   # 左上，右上，右下，左下
  34.     box4 = [12, 5, 20, 2, 20, 15, 12, 15]
  35.     iou = bbox_iou_eval(box3, box4)
  36.     print(iou)

 

参考：IOU交并比的计算

关于计算交集面积的代码看到一篇，还没有验证：Gym 100952J&&2015 HIAST Collegiate Programming Contest J. Polygons Intersection【计算几何求解两个凸多边形的相交面积板子题】

  1. #include "iostream"
  2. #include "string.h"
  3. #include "stack"
  4. #include "queue"
  5. #include "string"
  6. #include "vector"
  7. #include "set"
  8. #include "map"
  9. #include "algorithm"
  10. #include "stdio.h"
  11. #include "math.h"
  12. #define ll long long
  13. #define bug(x) cout<<x<<" "<<"UUUUU"<<endl;
  14. #define mem(a) memset(a,0,sizeof(a))
  15. #define mp(x,y) make_pair(x,y)
  16. using namespace std;
  17. const long long INF = 1e18+1LL;
  18. const int inf = 1e9+1e8;
  19. const int N=1e5+100;
  20. #define maxn 510
  21. const double eps=1E-8;
  22. int sig(double d){
  23.     return(d>eps)-(d<-eps);
  24. }
  25. struct Point{
  26.     double x,y; Point(){}
  27.     Point(double x,double y):x(x),y(y){}
  28.     bool operator==(const Point&p)const{
  29.         return sig(x-p.x)==0&&sig(y-p.y)==0;
  30.     }
  31. };
  32. double cross(Point o,Point a,Point b){
  33.     return(a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
  34. }
  35. double area(Point* ps,int n){
  36.     ps[n]=ps[0];
  37.     double res=0;
  38.     for(int i=0;i<n;i++){
  39.         res+=ps[i].x*ps[i+1].y-ps[i].y*ps[i+1].x;
  40.     }
  41.     return res/2.0;
  42. }
  43. int lineCross(Point a,Point b,Point c,Point d,Point&p){
  44.     double s1,s2;
  45.     s1=cross(a,b,c);
  46.     s2=cross(a,b,d);
  47.     if(sig(s1)==0&&sig(s2)==0) return 2;
  48.     if(sig(s2-s1)==0) return 0;
  49.     p.x=(c.x*s2-d.x*s1)/(s2-s1);
  50.     p.y=(c.y*s2-d.y*s1)/(s2-s1);
  51.     return 1;
  52. }
  53. //多边形切割
  54. //用直线ab切割多边形p，切割后的在向量(a,b)的左侧，并原地保存切割结果
  55. //如果退化为一个点，也会返回去,此时n为1
  56. void polygon_cut(Point*p,int&n,Point a,Point b){
  57.     static Point pp[maxn];
  58.     int m=0;p[n]=p[0];
  59.     for(int i=0;i<n;i++){
  60.         if(sig(cross(a,b,p[i]))>0) pp[m++]=p[i];
  61.         if(sig(cross(a,b,p[i]))!=sig(cross(a,b,p[i+1])))
  62.             lineCross(a,b,p[i],p[i+1],pp[m++]);
  63.     }
  64.     n=0;
  65.     for(int i=0;i<m;i++)
  66.         if(!i||!(pp[i]==pp[i-1]))
  67.             p[n++]=pp[i];
  68.     while(n>1&&p[n-1]==p[0])n--;
  69. }
  70. //---------------华丽的分隔线-----------------//
  71. //返回三角形oab和三角形ocd的有向交面积,o是原点//
  72. double intersectArea(Point a,Point b,Point c,Point d){
  73.     Point o(0,0);
  74.     int s1=sig(cross(o,a,b));
  75.     int s2=sig(cross(o,c,d));
  76.     if(s1==0||s2==0)return 0.0;//退化，面积为0
  77.     if(s1==-1) swap(a,b);
  78.     if(s2==-1) swap(c,d);
  79.     Point p[10]={o,a,b};
  80.     int n=3;
  81.     polygon_cut(p,n,o,c);
  82.     polygon_cut(p,n,c,d);
  83.     polygon_cut(p,n,d,o);
  84.     double res=fabs(area(p,n));
  85.     if(s1*s2==-1) res=-res;return res;
  86. }
  87. //求两多边形的交面积
  88. double intersectArea(Point*ps1,int n1,Point*ps2,int n2){
  89.     if(area(ps1,n1)<0) reverse(ps1,ps1+n1);
  90.     if(area(ps2,n2)<0) reverse(ps2,ps2+n2);
  91.     ps1[n1]=ps1[0];
  92.     ps2[n2]=ps2[0];
  93.     double res=0;
  94.     for(int i=0;i<n1;i++){
  95.         for(int j=0;j<n2;j++){
  96.             res+=intersectArea(ps1[i],ps1[i+1],ps2[j],ps2[j+1]);
  97.         }
  98.     }
  99.     return res;//assumeresispositive!
  100. }
  101. //hdu-3060求两个任意简单多边形的并面积
  102. Point ps1[maxn],ps2[maxn];
  103. int n1,n2;
  104. int main(){
  105.     int t;
  106.     cin>>t;
  107.     while(t--){
  108.         scanf("%d%d",&n1,&n2);
  109.         for(int i=0;i<n1;i++)
  110.             scanf("%lf%lf",&ps1[i].x,&ps1[i].y);
  111.         for(int i=0;i<n2;i++)
  112.             scanf("%lf%lf",&ps2[i].x,&ps2[i].y);
  113.         double ans=intersectArea(ps1,n1,ps2,n2);
  114.         //ans=fabs(area(ps1,n1))+fabs(area(ps2,n2))-ans;//容斥
  115.         printf("%.4f\n",ans);
  116.     }
  117.     return 0;
  118. }

运行输入和结果如下（其中前四行是输入，最后一行是输出）：

另外还看到一篇计算IOU的代码：https://github.com/CAPTAIN-WHU/DOTA_devkit/blob/master/polyiou.cpp

 

  1. #include<cstdio>
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cmath>
  5. #include <vector>
  6. using namespace std;
  7. #define maxn 51
  8. const double eps=1E-8;
  9. int sig(double d){
  10.     return(d>eps)-(d<-eps);
  11. }
  12. struct Point{
  13.     double x,y; Point(){}
  14.     Point(double x,double y):x(x),y(y){}
  15.     bool operator==(const Point&p)const{
  16.         return sig(x-p.x)==0&&sig(y-p.y)==0;
  17.     }
  18. };
  19. double cross(Point o,Point a,Point b){  //叉积
  20.     return(a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
  21. }
  22. double area(Point* ps,int n){
  23.     ps[n]=ps[0];
  24.     double res=0;
  25.     for(int i=0;i<n;i++){
  26.         res+=ps[i].x*ps[i+1].y-ps[i].y*ps[i+1].x;
  27.     }
  28.     return res/2.0;
  29. }
  30. int lineCross(Point a,Point b,Point c,Point d,Point&p){
  31.     double s1,s2;
  32.     s1=cross(a,b,c);
  33.     s2=cross(a,b,d);
  34.     if(sig(s1)==0&&sig(s2)==0) return 2;
  35.     if(sig(s2-s1)==0) return 0;
  36.     p.x=(c.x*s2-d.x*s1)/(s2-s1);
  37.     p.y=(c.y*s2-d.y*s1)/(s2-s1);
  38.     return 1;
  39. }
  40. //多边形切割
  41. //用直线ab切割多边形p，切割后的在向量(a,b)的左侧，并原地保存切割结果
  42. //如果退化为一个点，也会返回去,此时n为1
  43. //void polygon_cut(Point*p,int&n,Point a,Point b){
  44. //    static Point pp[maxn];
  45. //    int m=0;p[n]=p[0];
  46. //    for(int i=0;i<n;i++){
  47. //        if(sig(cross(a,b,p[i]))>0) pp[m++]=p[i];
  48. //        if(sig(cross(a,b,p[i]))!=sig(cross(a,b,p[i+1])))
  49. //            lineCross(a,b,p[i],p[i+1],pp[m++]);
  50. //    }
  51. //    n=0;
  52. //    for(int i=0;i<m;i++)
  53. //        if(!i||!(pp[i]==pp[i-1]))
  54. //            p[n++]=pp[i];
  55. //    while(n>1&&p[n-1]==p[0])n--;
  56. //}
  57. void polygon_cut(Point*p,int&n,Point a,Point b, Point* pp){
  58. //    static Point pp[maxn];
  59.     int m=0;p[n]=p[0];
  60.     for(int i=0;i<n;i++){
  61.         if(sig(cross(a,b,p[i]))>0) pp[m++]=p[i];
  62.         if(sig(cross(a,b,p[i]))!=sig(cross(a,b,p[i+1])))
  63.             lineCross(a,b,p[i],p[i+1],pp[m++]);
  64.     }
  65.     n=0;
  66.     for(int i=0;i<m;i++)
  67.         if(!i||!(pp[i]==pp[i-1]))
  68.             p[n++]=pp[i];
  69.     while(n>1&&p[n-1]==p[0])n--;
  70. }
  71. //---------------华丽的分隔线-----------------//
  72. //返回三角形oab和三角形ocd的有向交面积,o是原点//
  73. double intersectArea(Point a,Point b,Point c,Point d){
  74.     Point o(0,0);
  75.     int s1=sig(cross(o,a,b));
  76.     int s2=sig(cross(o,c,d));
  77.     if(s1==0||s2==0)return 0.0;//退化，面积为0
  78.     if(s1==-1) swap(a,b);
  79.     if(s2==-1) swap(c,d);
  80.     Point p[10]={o,a,b};
  81.     int n=3;
  82.     Point pp[maxn];
  83.     polygon_cut(p,n,o,c, pp);
  84.     polygon_cut(p,n,c,d, pp);
  85.     polygon_cut(p,n,d,o, pp);
  86.     double res=fabs(area(p,n));
  87.     if(s1*s2==-1) res=-res;return res;
  88. }
  89. //求两多边形的交面积
  90. double intersectArea(Point*ps1,int n1,Point*ps2,int n2){
  91.     if(area(ps1,n1)<0) reverse(ps1,ps1+n1);
  92.     if(area(ps2,n2)<0) reverse(ps2,ps2+n2);
  93.     ps1[n1]=ps1[0];
  94.     ps2[n2]=ps2[0];
  95.     double res=0;
  96.     for(int i=0;i<n1;i++){
  97.         for(int j=0;j<n2;j++){
  98.             res+=intersectArea(ps1[i],ps1[i+1],ps2[j],ps2[j+1]);
  99.         }
  100.     }
  101.     return res;//assumeresispositive!
  102. }
  103.  
  104.  
  105.  
  106.  
  107. double iou_poly(vector<double> p, vector<double> q) {
  108.     Point ps1[maxn],ps2[maxn];
  109.     int n1 = 4;
  110.     int n2 = 4;
  111.     for (int i = 0; i < 4; i++) {
  112.         ps1[i].x = p[i * 2];
  113.         ps1[i].y = p[i * 2 + 1];
  114.  
  115.         ps2[i].x = q[i * 2];
  116.         ps2[i].y = q[i * 2 + 1];
  117.     }
  118.     double inter_area = intersectArea(ps1, n1, ps2, n2);
  119.     double union_area = fabs(area(ps1, n1)) + fabs(area(ps2, n2)) - inter_area;
  120.     double iou = inter_area / union_area;
  121.  
  122. //    cout << "inter_area:" << inter_area << endl;
  123. //    cout << "union_area:" << union_area << endl;
  124. //    cout << "iou:" << iou << endl;
  125.  
  126.     return iou;
  127. }
  128. //
  129. //int main(){
  130. //    double p[8] = {0, 0, 1, 0, 1, 1, 0, 1};
  131. //    double q[8] = {0.5, 0.5, 1.5, 0.5, 1.5, 1.5, 0.5, 1.5};
  132. //    vector<double> P(p, p + 8);
  133. //    vector<double> Q(q, q + 8);
  134. //    iou_poly(P, Q);
  135. //    return 0;
  136. //}
  137.  
  138. //int main(){
  139. //    double p[8] = {0, 0, 1, 0, 1, 1, 0, 1};
  140. //    double q[8] = {0.5, 0.5, 1.5, 0.5, 1.5, 1.5, 0.5, 1.5};
  141. //    iou_poly(p, q);
  142. //    return 0;
  143. //}

其头文件：https://github.com/CAPTAIN-WHU/DOTA_devkit/blob/master/polyiou.h

  1. //
  2. // Created by dingjian on 18-2-3.
  3. //
  4.  
  5. #ifndef POLYIOU_POLYIOU_H
  6. #define POLYIOU_POLYIOU_H
  7.  
  8. #include <vector>
  9. double iou_poly(std::vector<double> p, std::vector<double> q);
  10. #endif //POLYIOU_POLYIOU_H

 

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

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号