• <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| 久久精品国产亚洲AV香蕉| 中文字幕亚洲综合久久| 国产AV影片久久久久久| 色偷偷88欧美精品久久久| 精品国产乱码久久久久久呢| 久久久久99精品成人片欧美| 久久国产成人| 久久国产高潮流白浆免费观看| 国产精品成人99久久久久| 一级女性全黄久久生活片免费| 久久综合久久自在自线精品自| 一本久久久久久久| 色欲综合久久中文字幕网| 精品国产热久久久福利| 亚洲AV乱码久久精品蜜桃| 久久久久女教师免费一区| 国产综合久久久久久鬼色| 亚洲人成无码久久电影网站| 香港aa三级久久三级| 日本久久久久亚洲中字幕| 久久天天婷婷五月俺也去| 国产呻吟久久久久久久92| 国产99精品久久| 久久亚洲精品人成综合网| 久久亚洲sm情趣捆绑调教| 久久午夜综合久久| 精品多毛少妇人妻AV免费久久| 久久中文字幕一区二区| 久久不见久久见免费视频7| 亚洲国产成人精品久久久国产成人一区二区三区综 | 少妇人妻综合久久中文字幕| 国产亚洲精久久久久久无码AV| 久久久女人与动物群交毛片| 婷婷五月深深久久精品| 久久妇女高潮几次MBA| 超级碰碰碰碰97久久久久| 大香伊人久久精品一区二区 | 色综合久久中文综合网| 国产精品一久久香蕉产线看| 国产精品青草久久久久婷婷|