设为首页收藏本站

中国膜结构网

 找回密码
 立即注册

QQ登录

只需一步,快速开始

膜结构车棚
膜结构车棚膜结构资质国产膜材 膜结构网中国膜结构协会
查看: 465|回复: 0

<计算几何>凸包-旋转卡壳最小面积外接矩形

[复制链接]
  • TA的每日心情
    开心
    2021-6-22 09:39
  • 签到天数: 1542 天

    [LV.Master]伴坛终老

    发表于 2020-11-24 22:14 | 显示全部楼层 |阅读模式
    <计算几何>凸包-旋转卡壳最小面积外接矩形
    1. #include <iostream>
    2. #include <cstdio>
    3. #include <cmath>
    4. #include <algorithm>
    5. #define min(x,y) ((x)<(y)?(x):(y))
    6. using namespace std;


    7. struct point
    8. {
    9.     double x,y;

    10.     point(){}
    11.     point(double _x,double _y)
    12.     {
    13.         x=_x;
    14.         y=_y;
    15.     }


    16.     void get()
    17.     {
    18.         scanf("%lf%lf",&x,&y);
    19.     }
    20. };

    21. int DB (double x)
    22. {
    23.     if(x>EPS) return 1;
    24.     if(x<-EPS) return -1;
    25.     return 0;
    26. }

    27. double cross(point a,point b,point p)
    28. {
    29.     return (b.x-a.x)*(p.y-a.y)-(b.y-a.y)*(p.x-a.x);
    30. }

    31. //向量点乘
    32. //ab*ac
    33. double dot(point a,point b,point c)   //求ac在ab边的摄影
    34. {
    35.     return (c.x-a.x)*(b.x-a.x)+(c.y-a.y)*(b.y-a.y);
    36. }
    37. //pt[]保存凸包,n为凸包顶点数
    38. double calMinRect(point pt[],int n)
    39. {
    40.     if(n<3) return 0;
    41.     int i,p=1,q=1,r;
    42.     double ans=1e10,a,b,c;
    43.     for(i=0;i<n;i++)
    44.     {
    45.         while(1)       //叉积求面积计算对踵点,图中点p
    46.         {
    47.             a=cross(pt[i],pt[i+1],pt[p+1]);
    48.             b=cross(pt[i],pt[i+1],pt[p]);
    49.             if(DB(a-b)<=0) break;    //叉积开始减小
    50.             p=(p+1)%n;
    51.         }
    52.         while(1)      //求以i为顶点,在(i,i+1)边摄影最靠右的点,图中点q
    53.         {
    54.             a=dot(pt[i],pt[i+1],pt[q+1]);
    55.             b=dot(pt[i],pt[i+1],pt[q]);
    56.             if(DB(a-b)<=0) break;    //点积开始减小
    57.             q=(q+1)%n;
    58.         }
    59.         if(!i)r=q;    //第一次循环时从q点开始找r点
    60.         while(1)      //求以i为顶点,在(i,i+1)边摄影最靠左的点,图中点r
    61.         {
    62.             a=dot(pt[i],pt[i+1],pt[r+1]);
    63.             b=dot(pt[i],pt[i+1],pt[r]);
    64.             if(DB(a-b)>0) break;     //点积开始增大
    65.             r=(r+1)%n;
    66.         }
    67.         a=cross(pt[i],pt[i+1],pt[p]);        //求出绿色平行四边形面积,大小等于雪青色矩形的面积
    68.         b=dot(pt[i],pt[i+1],pt[q])-dot(pt[i],pt[i+1],pt[r]);      //两摄影相减,求出红色(待求)矩形底边长
    69.         c=dot(pt[i],pt[i+1],pt[i+1]);        //(i,i+1)边在自身上的投影,即计算(i,i+1)边的长度
    70.         ans=min(ans,a*b/c);         //雪青色矩形与红色矩形高相同,面积比为底边长之比
    71.     }
    72.     return ans;
    73. }



    74. //旋转卡壳最小面积外接矩形
    75. #define min(x,y) ((x)<(y)?(x):(y))

    76. struct Point
    77. {
    78.     double x,y;
    79. }ch[1005];

    80. int DB (double d)
    81. {
    82.         if (fabs(d)<1e-8)
    83.                 return 0;
    84.         return d>0?1:-1;
    85. }

    86. double cross (Point p,Point ch,Point x)
    87. {
    88.         return (p.x-x.x)*(ch.y-x.y)-(ch.x-x.x)*(p.y-x.y);
    89. }

    90. double dot(Point a,Point b,Point c)   //求ac在ab边的摄影
    91. {
    92.     return (c.x-a.x)*(b.x-a.x)+(c.y-a.y)*(b.y-a.y);
    93. }

    94. double CalMinRect (Point ch[],int n)
    95. {
    96.     if(n<3) return 0;
    97.     int i,p=1,q=1,r;
    98.     double ans=1e10,a,b,c;
    99.     for(i=0;i<n;i++)
    100.     {
    101.                 while (DB(cross(ch[i+1],ch[p+1],ch[i])-cross(ch[i+1],ch[p],ch[i])) == 1)
    102.             p=(p+1)%n;
    103.         while (DB(dot(ch[i],ch[i+1],ch[q+1])-dot(ch[i],ch[i+1],ch[q])) == 1)
    104.             q=(q+1)%n;
    105.         if (i == 0)
    106.                         r=q;
    107.         while(DB(dot(ch[i],ch[i+1],ch[r+1])-dot(ch[i],ch[i+1],ch[r])) <= 0)
    108.             r=(r+1)%n;

    109.         a=cross(ch[i],ch[i+1],ch[p]);
    110.         b=dot(ch[i],ch[i+1],ch[q])-dot(ch[i],ch[i+1],ch[r]);
    111.         c=dot(ch[i],ch[i+1],ch[i+1]);
    112.         ans=min(ans,a*b/c);
    113.     }
    114.     return ans;
    115. }
    复制代码
    回复


    http://www.mjgw.org/ 专业从事膜结构设计、制作加工、施工安装的膜结构工程服务,能够为客户提供专业的膜结构整体解决方案。做中国最好的膜结构综合服务平台。欢迎大家联系电话:198-7840-1958,QQ:463017170.
    相关关键词:膜结构车棚,膜结构车棚覆盖,膜结构车棚公司,膜结构车棚多少钱,膜结构车棚厂家,膜结构车棚价格,社区膜结构车棚,膜结构车棚膜布厂家 ,膜结构车棚哪家好,膜结构车棚多少钱一米,膜结构车棚报价,膜结构车棚哪里有,膜结构车棚定制,膜结构车棚安装,膜结构车棚设计,膜结构车棚电话,膜结构车棚加工,膜结构车棚膜布价格,膜结构车棚批发,膜结构车棚制造商,膜结构车棚生产厂家,膜结构车棚设计,膜结构车棚施工,膜结构车棚多少钱一平米,膜结构车棚订制,张拉膜车棚,张拉膜车棚覆盖,张拉膜车棚公司,张拉膜车棚多少钱,张拉膜车棚厂家,张拉膜车棚价格,社区张拉膜车棚,张拉膜车棚膜布厂家 ,张拉膜车棚哪家好,张拉膜车棚多少钱一米,张拉膜车棚报价,张拉膜车棚哪里有,张拉膜车棚定制,张拉膜车棚安装,张拉膜车棚设计,张拉膜车棚电话,张拉膜车棚加工,张拉膜车棚膜布价格,张拉膜车棚批发,张拉膜车棚制造商,张拉膜车棚生产厂家,张拉膜车棚设计,张拉膜车棚施工,张拉膜车棚多少钱一平米,张拉膜车棚订制,常用膜材品牌:德国杜肯、法国法拉利、德国海德斯、德国米乐、日本平岗、韩国秀博、比利时希运、美国赫虏伯、中国科宝、上海慧遥。

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    关闭

    推荐膜材品牌上一条 /6 下一条

    进口膜材 国产膜材 pvdf膜材ptfe膜材ETFE膜材
    最好的膜结构公司 一级膜结构资质 膜结构一级资质
    膜结构设计-膜结构十大品牌-etfe设计-充气膜结构
    诺科膜结构
    遨都膜结构设计
    中国膜结构网
    中国空间膜结构

    QQ|申请友链|手机版|中国膜结构论坛