• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Why so serious? --[NKU]schindlerlee

            2010-06-16 12:04:40 pku3528 三維凸包


            三維凸包的求解如果有四點共面,那么就比較繁瑣了。
            增量法,每次添加一個點,然后更新凸包。
            關(guān)于增量法的圖示看這里:
            http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html

            現(xiàn)在的主要問題就是,一直所有面的法向量,如何更新凸包。
            法向量點乘一個向量,可以得到這個向量在法向量上的偏移,如果這個偏移是正的,說明這個向量相關(guān)的點在面的上方,負的是下方,所以只要找到一條邊關(guān)聯(lián)的兩個面的點積是一正一負即可。

            注意這里的所有面都是由三個點組成,且是有序的,每個邊只被記錄兩次,一次順時針,一次逆時針。
            這里不能使用int,數(shù)值太大會越界。

            ?1?
            ?2?const?int?N?=?1024;
            ?3?struct?F?{
            ?4?????int?v[4];
            ?5?????F(){}
            ?6?????F(int?a,int?b,int?c){?v[0]?=?a,?v[1]?=?b,?v[2]?=?c,?v[3]?=?v[0];}
            ?7?};
            ?8?
            ?9?struct?point_t?{
            10?????double?x,?y,?z;
            11?????point_t?(){}
            12?????point_t?(double?a,?double?b,?double?c){x?=?a,?y?=?b,?z?=?c;}
            13?};
            14?point_t?operator?+(point_t?a,?point_t?b)?{?return?point_t?(a.x?+?b.x,?a.y?+?b.y,?a.z?+?b.z);}
            15?point_t?operator?-(point_t?a,?point_t?b)?{?return?point_t?(a.x?-?b.x,?a.y?-?b.y,?a.z?-?b.z);}
            16?
            17?double?dot_mul(point_t?a,?point_t?b)?{?return?a.x?*?b.x?+?a.y?*?b.y?+?a.z?*?b.z;}
            18?point_t?cross_mul(point_t?a,point_t?b)
            19?{
            20?????return?point_t?(a.y*b.z?-?b.y*a.z?,
            21?????????????????????a.z*b.x?-?b.z*a.x?,
            22?????????????????????a.x*b.y?-?b.x*a.y);
            23?}
            24?
            25?double?area(point_t?a,?point_t?b)
            26?{
            27???point_t?v?=?cross_mul(a,?b);
            28???return?sqrt(0.0?+?v.x?*?v.x?+?v.y?*?v.y?+?v.z?*?v.z)?/?2;
            29?}
            30?
            31?point_t?p[N];
            32?int?vis[N][N],?n;
            33?
            34?int?main()
            35?{
            36???int?i,?j,?k;
            37???scanf("%d",?&n);
            38???for?(i?=?0;i?<?n;i++)?{
            39???????scanf("%lf?%lf?%lf",?&p[i].x,?&p[i].y,?&p[i].z);
            40???}
            41???vector<F>?cur;
            42???cur.pb(F(0,?1,?2)),?cur.pb(F(2,?1,?0));
            43???for?(i?=?3;i?<?n;i++)?{
            44???????vector<F>?next;
            45???????for?(j?=?0;j?<?cur.size();j++)?{
            46???????????F?f?=?cur[j];
            47???????????point_t?v?=?cross_mul(p[f.v[1]]?-?p[f.v[0]],
            48?????????????????????????????????p[f.v[2]]?-?p[f.v[1]]);
            49???????????int?val?=?dot_mul(v,?p[i]?-?p[f.v[1]])?<?0???-1?:?1;
            50???????????if?(val?<?0)?{
            51???????????????next.pb(f);
            52???????????}
            53???????????for?(k?=?0;k?<?3;k++)?{
            54???????????????if?(vis[f.v[k+1]][f.v[k]]?==?0)?{
            55???????????????????vis[f.v[k]][f.v[k+1]]?=?val;
            56???????????????}else?{ //http://m.shnenglu.com/schindlerlee
            57???????????????????if?(vis[f.v[k+1]][f.v[k]]?!=?val)?{
            58???????????????????????if?(val?>?0)?{
            59???????????????????????????next.pb(F(f.v[k],?f.v[k+1],?i));
            60???????????????????????}else?{
            61???????????????????????????next.pb(F(f.v[k+1],?f.v[k],?i));
            62???????????????????????}
            63???????????????????}
            64???????????????????vis[f.v[k+1]][f.v[k]]?=?0;
            65???????????????}
            66???????????}
            67???????}
            68???????cur?=?next;
            69???}
            70???double?ans?=?0;
            71???for?(i?=?0;i?<?cur.size();i++)?{
            72???????F?f?=?cur[i];
            73???????ans?+=?area(p[f.v[0]]?-?p[f.v[1]],?p[f.v[2]]?-?p[f.v[1]]);
            74???}
            75???printf("%.3f\n",?ans);
            76???return?0;
            77?}


            posted on 2010-06-16 12:02 schindlerlee 閱讀(2110) 評論(2)  編輯 收藏 引用 所屬分類: 解題報告

            Feedback

            # re: 2010-06-16 12:04:40 pku3528 三維凸包 2010-06-18 13:37 AngelClover

            你這是啥復(fù)雜度  回復(fù)  更多評論   

            # re: 2010-06-16 12:04:40 pku3528 三維凸包 2010-06-18 16:03 schindlerlee

            @AngelClover
            O(n^2)  回復(fù)  更多評論   

            亚洲伊人久久成综合人影院| 国产三级久久久精品麻豆三级| 亚洲AV无码久久精品狠狠爱浪潮| 久久强奷乱码老熟女网站| 91久久精一区二区三区大全| 亚洲成色WWW久久网站| 午夜精品久久久久久毛片| 中文无码久久精品| 伊人色综合久久天天人手人婷| 区久久AAA片69亚洲| 亚洲熟妇无码另类久久久| 亚洲综合熟女久久久30p| 久久亚洲日韩精品一区二区三区| 亚洲国产欧洲综合997久久| 久久久久无码精品国产| 久久精品国产亚洲综合色| 99久久国产主播综合精品| 久久国产高清一区二区三区| 色综合久久夜色精品国产| 国产毛片欧美毛片久久久| 精品永久久福利一区二区| 精品久久久久久无码人妻热| 亚洲精品国产第一综合99久久| 偷偷做久久久久网站| 久久久久女人精品毛片| 国产日韩久久免费影院| 久久久午夜精品| 精品国产福利久久久| 欧美性大战久久久久久| 亚洲国产精品无码成人片久久| 精品久久久久久国产91| 久久综合色老色| 久久91精品国产91久久麻豆| 蜜桃麻豆www久久国产精品| 久久久精品国产sm调教网站 | 久久精品国产精品亚洲毛片| 久久精品中文字幕久久| A级毛片无码久久精品免费 | 伊人久久大香线焦综合四虎 | 伊人久久大香线蕉AV色婷婷色| 久久99国产精品久久99果冻传媒|