• <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 閱讀(2104) 評論(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)  回復  更多評論   

            亚洲国产精品久久久久婷婷软件| 久久久久久久久波多野高潮| 国产精品伦理久久久久久| 日韩一区二区久久久久久| 99久久精品免费国产大片| 久久99精品国产麻豆婷婷| 亚洲午夜无码久久久久小说| 亚洲国产美女精品久久久久∴ | 久久夜色精品国产噜噜亚洲a| 亚洲精品97久久中文字幕无码| 亚洲αv久久久噜噜噜噜噜| 青青草原综合久久| 久久精品国产亚洲AV香蕉| 精品久久国产一区二区三区香蕉| 精品多毛少妇人妻AV免费久久 | 国产精品久久成人影院| 久久AAAA片一区二区| 亚洲αv久久久噜噜噜噜噜| 久久久精品国产亚洲成人满18免费网站 | 品成人欧美大片久久国产欧美| 国产A三级久久精品| 久久久久亚洲av毛片大| 97久久精品午夜一区二区| 综合人妻久久一区二区精品| 久久久网中文字幕| 99久久国产综合精品网成人影院| 久久偷看各类wc女厕嘘嘘| 久久天天躁狠狠躁夜夜躁2014| 久久久久女教师免费一区| 国产免费久久精品99久久| 青青草国产成人久久91网| 91精品国产乱码久久久久久 | 国产精品VIDEOSSEX久久发布| 久久精品国产亚洲AV电影| 国产成人精品综合久久久| 国产成人久久精品一区二区三区 | 东方aⅴ免费观看久久av| 国产精品亚洲综合久久| 大香伊人久久精品一区二区| 亚洲?V乱码久久精品蜜桃| 久久毛片一区二区|