设为首页收藏本站

中国膜结构网

 找回密码
 立即注册

QQ登录

只需一步,快速开始

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

点集的最小面积包围矩形

[复制链接]
  • TA的每日心情
    开心
    2021-6-19 14:40
  • 签到天数: 1539 天

    [LV.Master]伴坛终老

    发表于 2020-11-24 22:11 | 显示全部楼层 |阅读模式
    点集的最小面积包围矩形
    1. typedef double typev;
    2. const double eps = 1e-8;
    3. const int N = 50005;
    4. int sign(double d){
    5.     return d < -eps ? -1 : (d > eps);
    6. }
    7. struct point{
    8.     typev x, y;
    9.     point operator-(point d){
    10.         point dd;
    11.         dd.x = this->x - d.x;
    12.         dd.y = this->y - d.y;
    13.         return dd;
    14.     }
    15.     point operator+(point d){
    16.         point dd;
    17.         dd.x = this->x + d.x;
    18.         dd.y = this->y + d.y;
    19.         return dd;
    20.     }
    21.     void read(){ scanf("%lf%lf", &x, &y); }
    22. }ps[N];
    23. int n, cn;
    24. double dist(point d1, point d2){
    25.     return sqrt(pow(d1.x - d2.x, 2.0) + pow(d1.y - d2.y, 2.0));
    26. }
    27. double dist2(point d1, point d2){
    28.     return pow(d1.x - d2.x, 2.0) + pow(d1.y - d2.y, 2.0);
    29. }
    30. bool cmp(point d1, point d2){
    31.     return d1.y < d2.y || (d1.y == d2.y && d1.x < d2.x);
    32. }
    33. //st1-->ed1叉乘st2-->ed2的值
    34. typev xmul(point st1, point ed1, point st2, point ed2){
    35.     return (ed1.x - st1.x) * (ed2.y - st2.y) - (ed1.y - st1.y) * (ed2.x - st2.x);
    36. }
    37. typev dmul(point st1, point ed1, point st2, point ed2){
    38.     return (ed1.x - st1.x) * (ed2.x - st2.x) + (ed1.y - st1.y) * (ed2.y - st2.y);
    39. }
    40. //多边形类
    41. struct poly{
    42.     static const int N = 50005; //点数的最大值
    43.     point ps[N+5]; //逆时针存储多边形的点,[0,pn-1]存储点
    44.     int pn;  //点数
    45.     poly() { pn = 0; }
    46.     //加进一个点
    47.     void push(point tp){
    48.         ps[pn++] = tp;
    49.     }
    50.     //第k个位置
    51.     int trim(int k){
    52.         return (k+pn)%pn;
    53.     }
    54.     void clear(){ pn = 0; }
    55. };
    56. //返回含有n个点的点集ps的凸包
    57. poly graham(point* ps, int n){
    58.     sort(ps, ps + n, cmp);
    59.     poly ans;
    60.     if(n <= 2){
    61.         for(int i = 0; i < n; i++){
    62.             ans.push(ps[i]);
    63.         }
    64.         return ans;
    65.     }
    66.     ans.push(ps[0]);
    67.     ans.push(ps[1]);
    68.     point* tps = ans.ps;
    69.     int top = -1;
    70.     tps[++top] = ps[0];
    71.     tps[++top] = ps[1];
    72.     for(int i = 2; i < n; i++){
    73.         while(top > 0 && xmul(tps[top - 1], tps[top], tps[top - 1], ps[i]) <= 0) top--;
    74.         tps[++top] = ps[i];
    75.     }
    76.     int tmp = top;  //注意要赋值给tmp!
    77.     for(int i = n - 2; i >= 0; i--){
    78.         while(top > tmp && xmul(tps[top - 1], tps[top], tps[top - 1], ps[i]) <= 0) top--;
    79.         tps[++top] = ps[i];
    80.     }
    81.     ans.pn = top;
    82.     return ans;
    83. }
    84. //求点p到st->ed的垂足,列参数方程
    85. point getRoot(point p, point st, point ed){
    86.     point ans;
    87.     double u=((ed.x-st.x)*(ed.x-st.x)+(ed.y-st.y)*(ed.y-st.y));
    88.     u = ((ed.x-st.x)*(ed.x-p.x)+(ed.y-st.y)*(ed.y-p.y))/u;
    89.     ans.x = u*st.x+(1-u)*ed.x;
    90.     ans.y = u*st.y+(1-u)*ed.y;
    91.     return ans;
    92. }
    93. //next为直线(st,ed)上的点,返回next沿(st,ed)右手垂直方向延伸l之后的点
    94. point change(point st, point ed, point next, double l){
    95.     point dd;
    96.     dd.x = -(ed - st).y;
    97.     dd.y = (ed - st).x;
    98.     double len = sqrt(dd.x * dd.x + dd.y * dd.y);
    99.     dd.x /= len, dd.y /= len;
    100.     dd.x *= l, dd.y *= l;
    101.     dd = dd + next;
    102.     return dd;
    103. }
    104. //求含n个点的点集ps的最小面积矩形,并把结果放在ds(ds为一个长度是4的数组即可,ds中的点是逆时针的)中,并返回这个最小面积。
    105. double getMinAreaRect(point* ps, int n, point* ds){
    106.     int cn, i;
    107.     double ans;
    108.     point* con;
    109.     poly tpoly = graham(ps, n);
    110.     con = tpoly.ps;
    111.     cn = tpoly.pn;
    112.     if(cn <= 2){
    113.         ds[0] = con[0]; ds[1] = con[1];
    114.         ds[2] = con[1]; ds[3] = con[0];
    115.         ans=0;
    116.     }else{
    117.         int  l, r, u;
    118.         double tmp, len;
    119.         con[cn] = con[0];
    120.         ans = 1e40;
    121.         l = i = 0;
    122.         while(dmul(con[i], con[i+1], con[i], con[l])
    123.             >= dmul(con[i], con[i+1], con[i], con[(l-1+cn)%cn])){
    124.                 l = (l-1+cn)%cn;
    125.         }
    126.         for(r=u=i = 0; i < cn; i++){
    127.             while(xmul(con[i], con[i+1], con[i], con[u])
    128.                 <= xmul(con[i], con[i+1], con[i], con[(u+1)%cn])){
    129.                     u = (u+1)%cn;
    130.             }
    131.             while(dmul(con[i], con[i+1], con[i], con[r])
    132.                 <= dmul(con[i], con[i+1], con[i], con[(r+1)%cn])){
    133.                     r = (r+1)%cn;
    134.             }
    135.             while(dmul(con[i], con[i+1], con[i], con[l])
    136.                 >= dmul(con[i], con[i+1], con[i], con[(l+1)%cn])){
    137.                     l = (l+1)%cn;
    138.             }
    139.             tmp = dmul(con[i], con[i+1], con[i], con[r]) - dmul(con[i], con[i+1], con[i], con[l]);
    140.             tmp *= xmul(con[i], con[i+1], con[i], con[u]);
    141.             tmp /= dist2(con[i], con[i+1]);
    142.             len = xmul(con[i], con[i+1], con[i], con[u])/dist(con[i], con[i+1]);
    143.             if(sign(tmp - ans) < 0){
    144.                 ans = tmp;
    145.                 ds[0] = getRoot(con[l], con[i], con[i+1]);
    146.                 ds[1] = getRoot(con[r], con[i+1], con[i]);
    147.                 ds[2] = change(con[i], con[i+1], ds[1], len);
    148.                 ds[3] = change(con[i], con[i+1], ds[0], len);
    149.             }
    150.         }
    151.     }
    152.     return ans+eps;
    153. }
    复制代码
    回复


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

    使用道具 举报

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

    本版积分规则

    关闭

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

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

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