• <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 三維凸包


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

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

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

            ?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://www.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 閱讀(2119) 評論(2)  編輯 收藏 引用 所屬分類: 解題報告

            Feedback

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

            你這是啥復雜度  回復  更多評論   

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

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

            91久久国产视频| 国产精品久久久久9999高清| 日日狠狠久久偷偷色综合96蜜桃| 久久久久国产日韩精品网站| 思思久久99热只有频精品66| 久久精品午夜一区二区福利| 久久伊人色| 久久A级毛片免费观看| 久久精品国产黑森林| 久久精品无码专区免费青青| 久久久久久久国产免费看| 亚洲αv久久久噜噜噜噜噜| 国产精品99久久不卡| 亚洲精品乱码久久久久66| 久久国产综合精品五月天| 97久久超碰国产精品2021| 久久伊人五月丁香狠狠色| 久久精品国产精品亚洲下载| 久久久噜噜噜久久中文福利| 国产欧美久久久精品影院| 久久精品国产清自在天天线| 久久综合丁香激情久久| 久久精品无码午夜福利理论片 | 91精品国产综合久久精品| 99久久做夜夜爱天天做精品| 久久国产乱子伦精品免费午夜| 久久99精品久久久久婷婷| 97精品依人久久久大香线蕉97| 久久精品无码一区二区三区免费| 久久亚洲国产精品一区二区| 2021少妇久久久久久久久久| 午夜不卡久久精品无码免费| 欧美成人免费观看久久| 久久精品中文字幕大胸| 久久免费看黄a级毛片| 狠狠色丁香婷婷久久综合| 伊人久久无码中文字幕| 久久妇女高潮几次MBA| 久久综合88熟人妻| 国产精品久久久久天天影视| 99久久成人18免费网站|