快速凸包算法

快速凸包算法第1頁，課件共24頁，創(chuàng)作于2023年2月第二章二維凸包第2頁，課件共24頁，創(chuàng)作于2023年2月2.4凸包的快速算法主要思想點集S的凸包是取決于凸包邊界附近的點逐步丟掉凸包內(nèi)部的點，只關(guān)注凸包附近的點，從而提高算法的效率最好情況O(nlogn)、最壞情況O(n2)第3頁，課件共24頁，創(chuàng)作于2023年2月2.4凸包的快速算法算法過程取兩個極端點，它們是最右最下點pdr和最左最上點pul有向直線pdrpul將整個凸包被劃分為右凸包和左凸包對右凸包和左凸包分別進行遞歸遞歸設(shè)S1是嚴(yán)格在直線pdrpul右邊的點集（S1可能是空集）在S1中尋找距離直線pdrpul最遠(yuǎn)的點，作為pdrpul右邊的一個極端點b連接pdr和b

，及b

和pul

把pdr右側(cè)的點集記為A，pul右側(cè)的點集的點記為B對邊pdr

b和點集A、對邊bpul

和點集B分別遞歸調(diào)用依次連接凸包上的頂點，得點集S1的凸包，即點集S的右凸包類似地，計算出點集S的左凸包，從而得到整個點集S的凸包第4頁，課件共24頁，創(chuàng)作于2023年2月2.4凸包的快速算法算法過程取兩個極端點，它們是最右最下點pdr和最左最上點pul有向直線pdrpul將整個凸包被劃分為右凸包和左凸包對右凸包和左凸包分別進行遞歸第5頁，課件共24頁，創(chuàng)作于2023年2月2.4凸包的快速算法算法過程遞歸設(shè)S1是嚴(yán)格在直線pdrpul右邊的點集（S1可能是空集）在S1中尋找距離直線pdrpul最遠(yuǎn)的點，作為pdrpul右邊的一個極端點b連接pdr和b

，及b

和pul

把pdrb右側(cè)的點集記為A，bpul右側(cè)的點集的點記為B對邊pdrb和點集A、對邊bpul

和點集B分別遞歸調(diào)用第6頁，課件共24頁，創(chuàng)作于2023年2月2.4凸包的快速算法最好情況出現(xiàn)在每次劃分均是平衡的,O(nlogn)最壞情況出現(xiàn)在每次劃分點的分布都很極端,O(n2)第7頁，課件共24頁，創(chuàng)作于2023年2月2.5Graham算法20世紀(jì)60年代末貝爾實驗室需要求解10,000個點的凸包O(n2)的方法太慢1972年Graham出O(nlogn)的二維凸包算法第8頁，課件共24頁，創(chuàng)作于2023年2月2.5Graham算法基本思想在凸包內(nèi)部找到一個點o如S中任何三個不共線的點的重心，O(1)將o作為極坐標(biāo)的中心，計算每個點的極角θ對S中的點按θ升序排列（如pi

，pi+1，

pi+2），O(nlogn)計算相鄰三點轉(zhuǎn)角的凹凸性，刪除內(nèi)凹的點O(n)當(dāng)點集內(nèi)不再包含內(nèi)凹的點時，得到凸包第9頁，課件共24頁，創(chuàng)作于2023年2月2.5Graham算法以極端點pi為初始點，依次對相鄰三個點pi

，pi+1和pi+2，計算pi

pi+1×pi+1pi+2如果在z軸上的投影大于零，即(pi

pi+1×pi+1pi+2)z＞0說明在pi+1

處左轉(zhuǎn)彎，多邊形在該點上外凸，暫時保留這三點前進一步，同樣去判斷相鄰三個點pi+1，pi+2和

pi+3如果(pi

pi+1×pi+1pi+2)z≤0說明在pi+1處右轉(zhuǎn)彎，多邊形在該點上內(nèi)凹，把pi+1點從多邊形邊界中刪除后退一步，同樣去判斷相鄰三個點pi-1，pi和

pi+2時間復(fù)雜度為線性O(shè)(n)第10頁，課件共24頁，創(chuàng)作于2023年2月凸包計算方法對比極端邊算法O(n3)禮品包裹算法O(n2)快速算法最好情況O(nlogn)、最壞情況O(n2)Graham算法排序計算O(nlogn)、執(zhí)行時間O(n)總的時間復(fù)雜度O(nlogn)第11頁，課件共24頁，創(chuàng)作于2023年2月第三章凸包擴展第12頁，課件共24頁，創(chuàng)作于2023年2月3.1多面體兩個集合是同胚的(homeomorphic)指它們之間存在一個連續(xù)的一一映射并且這個映射的逆映射也是連續(xù)的兩個同胚的集合允許它們各自拉伸和扭曲，但只要不撕裂，其結(jié)果仍然同胚如果任一集合被撕裂了，映射的連續(xù)性便被破壞，兩個集合就不再同胚了第13頁，課件共24頁，創(chuàng)作于2023年2月3.1多面體兩個集合是同胚的(homeomorphic)三黑點的鄰域都不能同胚于一個三維的半開半閉的半球a和b中黑點的鄰域同胚于兩個接觸于一條線或一個點的三維的半開半閉的半球c中黑點的鄰域是同胚于半個二維開圓盤第14頁，課件共24頁，創(chuàng)作于2023年2月3.1多面體3.1.1多面體定義三維空間中的多面體是由有限個平面多邊形圍成的區(qū)域，其邊界滿足下列三個條件多面體表面上的每一對面，它們或者是分離的、或者有一個公共頂點、或者有一條公共的邊如果把多面體看成一個實心的實體，表面上任一點的足夠小的鄰域同胚于一個三維的如下定義的半開半閉的半球。半開半閉的半球定義為x2+y2+z2＜r2和z≤０的交，其中r為半球的半徑多面體表面是連通的，即表面上任意兩點可通過完全在表面上的路徑連接第15頁，課件共24頁，創(chuàng)作于2023年2月3.1多面體如果把多面體看成厚度為零的多邊形圍成的空間，第二個條件也可寫為多面體表面上任一點，它在表面上的鄰域同胚于一個開圓盤，開圓盤是二維的開圓如果一個表面上的每一個點都滿足這個條件，那么這個表面就被稱為二維流形(2Dmanifold)第16頁，課件共24頁，創(chuàng)作于2023年2月3.1多面體第３個條件表示頂點和邊組成的圖是連通的排除那些有“浮在”表面里面的頂點和邊的物體第17頁，課件共24頁，創(chuàng)作于2023年2月3.1多面體多面體可以存在“通孔(hole)”，從多面體表面的一面通到另一面多面體允許有任意多個這樣的孔，孔的數(shù)目叫做這個體的虧格(genus)虧格為0的多面體在拓?fù)渖贤哂谇蛱澑駷?的多面體在拓?fù)渖贤哂趫A環(huán)面凸多面體又叫做多胞形，為了強調(diào)它們是三維的，有時也叫做三胞形多胞形是凸多面體，連接它上面的任意兩個點的線段都在多胞形內(nèi)部凸多邊形在每一個頂點處是凸的多胞形在每一條邊處的所有二面角(dihedral)都是凸的(≤π)二面角是指空間中兩個相鄰接的面在它們的公共邊上的內(nèi)夾角對于任意的多胞形，頂點處的所有多邊形內(nèi)角之和小于2π這是每個頂點處是凸的必要條件，但不是充分條件第18頁，課件共24頁，創(chuàng)作于2023年2月3.1多面體3.1.2正則多面體只存在五種不同的正多面體正四面體、正六體、正八面體、正十二面體和正二十面體也叫柏拉圖體(Platonicsolids)，因為柏拉圖在他的《蒂邁歐篇(Timaeus)》中討論過它們第19頁，課件共24頁，創(chuàng)作于2023年2月3.1多面體3.1.3多面體的歐拉公式1758年，LeonardEuler虧格為0的多面體的頂點數(shù)、邊數(shù)和面數(shù)規(guī)律頂點數(shù)和面數(shù)之和總是比邊數(shù)多2正方體有8個頂點和6個面，8+6=14，比邊數(shù)12大2用v、e、f分別表示多面體頂點、邊和面的數(shù)目歐拉公式：v–e+f=2定理3.1對于一個頂點數(shù)v=n，邊數(shù)與面數(shù)分別為e和f的虧格為0的多面體，有v–e+f=2，且e和f都為O(n)第20頁，課件共24頁，創(chuàng)作于2023年2月3.2三維凸包算法3.2.1禮品包裹算法禮品包裹算法適用于任意維點集的凸包構(gòu)建三維禮品包裹算法是二維的直接擴展二維禮品包裹算法從凸包的一條邊開始三維禮品包裹算法從凸包的一個面f開始選擇面f上的一條邊e將f所在的平面π，沿著e朝著點集折疊，直至碰到第一個點p，則{p，e}成為凸包的一個新的三角面片重復(fù)上述操作第21頁，課件共24頁，創(chuàng)作于2023年2月3.2三維凸包算法3.2.1禮品包裹算法算法起始需要確定凸包上的一個面f首先把點集中的所有三維點投影到y(tǒng)z坐標(biāo)平面上得到一個二維點集然后求這個點集在二維空間中的一條極端邊，要求該邊的一個端點是z坐標(biāo)最小的一個點設(shè)這極端邊的兩個端點對應(yīng)的三維點為pi和pj，則pipj為三維空間中點集凸包的一條邊構(gòu)造一平面π通過pipj且其法線垂直x坐標(biāo)軸再對π繞著pipj旋轉(zhuǎn)，直至碰到第一個點p則{p，pipj}便是平面f第22頁，課件共24頁，創(chuàng)作于2023年2月3.2三維凸包算法3.2.1禮品包裹算法確定一個面片需要O(n)時間設(shè)F為凸包上面片的數(shù)目三維禮品包