1、快速凸包算法第1頁，共24頁，2022年，5月20日，10點(diǎn)22分，星期三第二章 二維凸包第2頁，共24頁，2022年，5月20日，10點(diǎn)22分，星期三2.4 凸包的快速算法主要思想點(diǎn)集S 的凸包是取決于凸包邊界附近的點(diǎn)逐步丟掉凸包內(nèi)部的點(diǎn)，只關(guān)注凸包附近的點(diǎn)，從而提高算法的效率最好情況O(nlogn)、 最壞情況O(n2)第3頁，共24頁，2022年，5月20日，10點(diǎn)22分，星期三2.4 凸包的快速算法算法過程取兩個極端點(diǎn)，它們是最右最下點(diǎn)pdr和最左最上點(diǎn)pul有向直線 pdr pul將整個凸包被劃分為右凸包和左凸包對右凸包和左凸包分別進(jìn)行遞歸遞歸設(shè)S1是嚴(yán)格在直線 pdr pul右邊的

2、點(diǎn)集（S1可能是空集）在S1中尋找距離直線 pdr pul最遠(yuǎn)的點(diǎn)，作為pdr pul右邊的一個極端點(diǎn)b連接pdr和b ，及b 和pul 把pdr右側(cè)的點(diǎn)集記為A， pul右側(cè)的點(diǎn)集的點(diǎn)記為B對邊pdr b和點(diǎn)集A、對邊b pul 和點(diǎn)集B分別遞歸調(diào)用依次連接凸包上的頂點(diǎn)，得點(diǎn)集S1的凸包，即點(diǎn)集S的右凸包類似地，計(jì)算出點(diǎn)集S的左凸包，從而得到整個點(diǎn)集S的凸包第4頁，共24頁，2022年，5月20日，10點(diǎn)22分，星期三2.4 凸包的快速算法算法過程取兩個極端點(diǎn)，它們是最右最下點(diǎn)pdr和最左最上點(diǎn)pul有向直線 pdr pul將整個凸包被劃分為右凸包和左凸包對右凸包和左凸包分別進(jìn)行遞歸第5頁，

3、共24頁，2022年，5月20日，10點(diǎn)22分，星期三2.4 凸包的快速算法算法過程遞歸設(shè)S1是嚴(yán)格在直線 pdr pul右邊的點(diǎn)集（S1可能是空集）在S1中尋找距離直線 pdr pul最遠(yuǎn)的點(diǎn)，作為 pdr pul右邊的一個極端點(diǎn)b連接 pdr和b ，及b 和 pul 把 pdrb右側(cè)的點(diǎn)集記為A， bpul右側(cè)的點(diǎn)集的點(diǎn)記為B對邊 pdrb和點(diǎn)集A、對邊bpul 和點(diǎn)集B分別遞歸調(diào)用第6頁，共24頁，2022年，5月20日，10點(diǎn)22分，星期三2.4 凸包的快速算法最好情況出現(xiàn)在每次劃分均是平衡的, O(nlogn)最壞情況出現(xiàn)在每次劃分點(diǎn)的分布都很極端, O(n2)第7頁，共24頁，20

4、22年，5月20日，10點(diǎn)22分，星期三2.5 Graham算法20世紀(jì)60年代末貝爾實(shí)驗(yàn)室需要求解10,000個點(diǎn)的凸包O(n2)的方法太慢1972年Graham出O(nlogn)的二維凸包算法第8頁，共24頁，2022年，5月20日，10點(diǎn)22分，星期三2.5 Graham算法基本思想在凸包內(nèi)部找到一個點(diǎn)o 如S 中任何三個不共線的點(diǎn)的重心，O(1)將o作為極坐標(biāo)的中心，計(jì)算每個點(diǎn)的極角對S中的點(diǎn)按升序排列（如pi ，pi+1 ， pi+2），O(nlogn)計(jì)算相鄰三點(diǎn)轉(zhuǎn)角的凹凸性，刪除內(nèi)凹的點(diǎn)O(n)當(dāng)點(diǎn)集內(nèi)不再包含內(nèi)凹的點(diǎn)時，得到凸包第9頁，共24頁，2022年，5月20日，10點(diǎn)2

5、2分，星期三2.5 Graham算法以極端點(diǎn) pi為初始點(diǎn)，依次對相鄰三個點(diǎn)pi ，pi+1和pi+2 ，計(jì)算pi pi+1pi+1pi+2如果在z 軸上的投影大于零，即(pi pi+1pi+1pi+2)z0說明在pi+1 處左轉(zhuǎn)彎，多邊形在該點(diǎn)上外凸，暫時保留這三點(diǎn)前進(jìn)一步，同樣去判斷相鄰三個點(diǎn)pi+1，pi+2和 pi+3如果(pi pi+1pi+1pi+2)z 0說明在pi+1處右轉(zhuǎn)彎，多邊形在該點(diǎn)上內(nèi)凹，把pi+1點(diǎn)從多邊形邊界中刪除后退一步，同樣去判斷相鄰三個點(diǎn)pi-1，pi和 pi+2時間復(fù)雜度為線性O(shè)(n)第10頁，共24頁，2022年，5月20日，10點(diǎn)22分，星期三凸包計(jì)算方

6、法對比極端邊算法O(n3)禮品包裹算法O(n2)快速算法最好情況O(nlogn)、 最壞情況O(n2)Graham 算法排序計(jì)算O(nlogn)、執(zhí)行時間O(n)總的時間復(fù)雜度O(nlogn)第11頁，共24頁，2022年，5月20日，10點(diǎn)22分，星期三第三章 凸包擴(kuò)展第12頁，共24頁，2022年，5月20日，10點(diǎn)22分，星期三3.1 多面體兩個集合是同胚的(homeomorphic)指它們之間存在一個連續(xù)的一一映射并且這個映射的逆映射也是連續(xù)的兩個同胚的集合允許它們各自拉伸和扭曲，但只要不撕裂，其結(jié)果仍然同胚如果任一集合被撕裂了，映射的連續(xù)性便被破壞，兩個集合就不再同胚了第13頁，共2

7、4頁，2022年，5月20日，10點(diǎn)22分，星期三3.1 多面體兩個集合是同胚的(homeomorphic)三黑點(diǎn)的鄰域都不能同胚于一個三維的半開半閉的半球a和b中黑點(diǎn)的鄰域同胚于兩個接觸于一條線或一個點(diǎn)的三維的半開半閉的半球c中黑點(diǎn)的鄰域是同胚于半個二維開圓盤第14頁，共24頁，2022年，5月20日，10點(diǎn)22分，星期三3.1 多面體3.1.1 多面體定義三維空間中的多面體是由有限個平面多邊形圍成的區(qū)域，其邊界滿足下列三個條件多面體表面上的每一對面，它們或者是分離的、或者有一個公共頂點(diǎn)、或者有一條公共的邊如果把多面體看成一個實(shí)心的實(shí)體，表面上任一點(diǎn)的足夠小的鄰域同胚于一個三維的如下定義的半

8、開半閉的半球。半開半閉的半球定義為x2+y2+z2r2和z的交，其中r為半球的半徑多面體表面是連通的，即表面上任意兩點(diǎn)可通過完全在表面上的路徑連接第15頁，共24頁，2022年，5月20日，10點(diǎn)22分，星期三3.1 多面體如果把多面體看成厚度為零的多邊形圍成的空間，第二個條件也可寫為多面體表面上任一點(diǎn)，它在表面上的鄰域同胚于一個開圓盤，開圓盤是二維的開圓如果一個表面上的每一個點(diǎn)都滿足這個條件，那么這個表面就被稱為二維流形(2D manifold)第16頁，共24頁，2022年，5月20日，10點(diǎn)22分，星期三3.1 多面體第個條件表示頂點(diǎn)和邊組成的圖是連通的排除那些有“浮在”表面里面的頂點(diǎn)和

9、邊的物體第17頁，共24頁，2022年，5月20日，10點(diǎn)22分，星期三3.1 多面體多面體可以存在“通孔(hole)”，從多面體表面的一面通到另一面多面體允許有任意多個這樣的孔，孔的數(shù)目叫做這個體的虧格(genus)虧格為0的多面體在拓?fù)渖贤哂谇蛱澑駷?的多面體在拓?fù)渖贤哂趫A環(huán)面凸多面體又叫做多胞形，為了強(qiáng)調(diào)它們是三維的，有時也叫做三胞形多胞形是凸多面體，連接它上面的任意兩個點(diǎn)的線段都在多胞形內(nèi)部凸多邊形在每一個頂點(diǎn)處是凸的多胞形在每一條邊處的所有二面角(dihedral)都是凸的()二面角是指空間中兩個相鄰接的面在它們的公共邊上的內(nèi)夾角對于任意的多胞形，頂點(diǎn)處的所有多邊形內(nèi)角之和小于2

10、這是每個頂點(diǎn)處是凸的必要條件，但不是充分條件第18頁，共24頁，2022年，5月20日，10點(diǎn)22分，星期三3.1 多面體3.1.2 正則多面體只存在五種不同的正多面體正四面體、正六體、正八面體、正十二面體和正二十面體也叫柏拉圖體(Platonic solids)，因?yàn)榘乩瓐D在他的蒂邁歐篇 (Timaeus) 中討論過它們第19頁，共24頁，2022年，5月20日，10點(diǎn)22分，星期三3.1 多面體3.1.3 多面體的歐拉公式1758年，Leonard Euler虧格為0的多面體的頂點(diǎn)數(shù)、邊數(shù)和面數(shù)規(guī)律頂點(diǎn)數(shù)和面數(shù)之和總是比邊數(shù)多2正方體有8個頂點(diǎn)和6個面，8+6=14，比邊數(shù)12大2用v、e

11、、f分別表示多面體頂點(diǎn)、邊和面的數(shù)目歐拉公式：v e + f = 2定理3.1 對于一個頂點(diǎn)數(shù)v=n，邊數(shù)與面數(shù)分別為e和f的虧格為0的多面體，有 v e + f = 2，且e和f都為O(n)第20頁，共24頁，2022年，5月20日，10點(diǎn)22分，星期三3.2 三維凸包算法3.2.1 禮品包裹算法禮品包裹算法適用于任意維點(diǎn)集的凸包構(gòu)建三維禮品包裹算法是二維的直接擴(kuò)展二維禮品包裹算法從凸包的一條邊開始三維禮品包裹算法從凸包的一個面f開始選擇面f上的一條邊e將f所在的平面，沿著e朝著點(diǎn)集折疊，直至碰到第一個點(diǎn)p，則p，e成為凸包的一個新的三角面片重復(fù)上述操作第21頁，共24頁，2022年，5月2

12、0日，10點(diǎn)22分，星期三3.2 三維凸包算法3.2.1 禮品包裹算法算法起始需要確定凸包上的一個面f首先把點(diǎn)集中的所有三維點(diǎn)投影到y(tǒng)z坐標(biāo)平面上得到一個二維點(diǎn)集然后求這個點(diǎn)集在二維空間中的一條極端邊，要求該邊的一個端點(diǎn)是z坐標(biāo)最小的一個點(diǎn)設(shè)這極端邊的兩個端點(diǎn)對應(yīng)的三維點(diǎn)為pi和pj，則pipj為三維空間中點(diǎn)集凸包的一條邊構(gòu)造一平面通過pipj且其法線垂直x坐標(biāo)軸再對繞著pipj旋轉(zhuǎn)，直至碰到第一個點(diǎn)p則p，pipj便是平面f第22頁，共24頁，2022年，5月20日，10點(diǎn)22分，星期三3.2 三維凸包算法3.2.1 禮品包裹算法確定一個面片需要O(n)時間設(shè)F為凸包上面片的數(shù)目三維禮品包裹算法時間復(fù)雜度為O(nF)三維禮品包