Day2計算幾何與三維凸包教學(xué)材料

專題討論：計算幾何與凸包算法AC_Aerolight2013.4.30Preface這一節(jié)的討論集中于幾個比較實(shí)用但關(guān)注度不高的凸包算法。穿插一些計算幾何基礎(chǔ)題目今天的目的依然是科普，因此內(nèi)容會比較簡單。已經(jīng)對相關(guān)內(nèi)容有所了解的同學(xué)可以跳過這些，但不要打擾其他同學(xué)。Let’sbegin.計算幾何基礎(chǔ)直線表示標(biāo)準(zhǔn)式Ax+By+C=0斜率式y(tǒng)=kx+b兩點(diǎn)式(x-x0)/(x1-x0)=(y-y0)/(y1-y0)x/A+y/B=1Balabala凸包：定義什么是凸多邊形Aspreciseasyoucan.對于形內(nèi)兩點(diǎn)X和Y，線段XY一定完全位于形內(nèi)對于多邊形的每條邊，整個多邊形都在其一側(cè)……凸包對于點(diǎn)集P，包含P的最小凸多邊形給定點(diǎn)集P=(Xi,Yi)，求點(diǎn)集P的凸包。增量法按輸入順序?qū)Ⅻc(diǎn)加入點(diǎn)集維護(hù)當(dāng)前點(diǎn)集的凸包(1)新點(diǎn)在凸包內(nèi)O(n)判定(2)新點(diǎn)在凸包外刪除從新點(diǎn)可見的凸包邊用鏈表維護(hù)凸包O(n)刪除和判斷O(n^2)在線算法增量法改進(jìn)時間復(fù)雜度用數(shù)據(jù)結(jié)構(gòu)分別維護(hù)上下凸殼O(nlogn)三點(diǎn)共線的情況可見性判定Javris步進(jìn)法（卷包裹法）假設(shè)有一根無限長的繩子，一開始繩子靠在點(diǎn)集的一個外圍點(diǎn)上。隨后繩子沿某個方向（如逆時針）繞動，直到碰到一個點(diǎn)之后停止繞動以新點(diǎn)為中心繼續(xù)沿指定方向繞動繩子當(dāng)回到起點(diǎn)時，得到凸包選取一個一定在凸包上的點(diǎn)X，沿著點(diǎn)集逆時針走一圈，當(dāng)走回X時，得到整個凸包(1)X怎么選？(2)如何找最右手邊的射線Javris步進(jìn)法（卷包裹法）復(fù)雜度分析O(n*h)H是凸包上的節(jié)點(diǎn)數(shù)Output-SensitiveGraham’sConvexHull目前使用最為廣泛的算法。確定極角序選取最左下的點(diǎn)作為參考點(diǎn)，按夾角對其他點(diǎn)排序按夾角排序？叉積定方向偏序關(guān)系Graham’sConvexHull維護(hù)凸殼節(jié)點(diǎn)按極角序入棧保持棧中節(jié)點(diǎn)凸殼性質(zhì)彈出棧頂元素直到新邊和原棧頂邊成左轉(zhuǎn)關(guān)系復(fù)雜度分析一個節(jié)點(diǎn)進(jìn)棧一次出棧一次，O(n)排序O(nlogn)總復(fù)雜度O(nlogn)常用技巧：維護(hù)水平序節(jié)點(diǎn)Divide-And-Conquer考慮對點(diǎn)集進(jìn)行分治Solve(S)返回S的凸包。Solve(S)將S分為兩個點(diǎn)集S1和S2，保證S1在S2左側(cè)合并Solve(S1)和Solve(S2)返回的凸包合并凸包的關(guān)鍵：找到切線上下切線可以分別考慮DIVIDE-AND-CONQUERU-,U,V和U,V,V+都成逆時針順序排列雙指針掃描從L的最右端和R的最左端開始維護(hù)U上可見點(diǎn)的最遠(yuǎn)點(diǎn)，直到一個點(diǎn)都看不見QuickHull回憶Quicksort選定一個標(biāo)準(zhǔn)mid，將<mid和>mid的部分分別排序定義過程QuickHull(a,b)保證A-B是凸包上的兩個頂點(diǎn)。定義點(diǎn)集S，使S中的點(diǎn)除了a,b以外都在a->b的右側(cè)。A-B這條邊被稱為凸包的弦(chord)QuickHull(a,b)應(yīng)當(dāng)返回S的凸包。QuickHullQuickHull(a,b)找到離ab最遠(yuǎn)的點(diǎn)c，那么c一定在凸包上QuickHull(a,c)QuickHull(c,b)將點(diǎn)集分成三個部分(1)三角形內(nèi)點(diǎn)(2)AC右側(cè)點(diǎn)(3)CB右側(cè)點(diǎn)對(2)(3)分治(1)的點(diǎn)全部拋棄(2)和(3)會有交集么？(1)(2)(3)ABCQuickHullQuickHull的效率三角形ABC內(nèi)的點(diǎn)一定不在凸包上在點(diǎn)集隨機(jī)的情況下，復(fù)雜度十分優(yōu)秀能夠被圓周撒點(diǎn)卡到O(nlogn)沒有點(diǎn)在三角形內(nèi)初始調(diào)用指定點(diǎn)集的最左/最右點(diǎn)x,y調(diào)用QuickHull(x,y)和QuickHull(y,x)去遞歸O(NlogN)Bound證明：凸包的時間復(fù)雜度不會低于O(nlogn)考慮點(diǎn)集Pi=(a[i],a[i]^2)對Pi求凸包，實(shí)際上就是對Ai的排序排序的復(fù)雜度不會低于O(nlogn)凸包的復(fù)雜度不會低于O(nlogn)NotOutput-SensitiveChan’sAlgorithm假設(shè)已知凸包上有M個點(diǎn)。Step1：將點(diǎn)均分為N/M個部分對每個點(diǎn)集進(jìn)行Graham-Scan，得到N/M個凸包復(fù)雜度統(tǒng)計O((n/m)*(mlogm))=O(nlogm)Step2：合并N/M個凸包。CHAN’SALGORITHMChan’sAlgorithmStep2：合并N/M個凸包卷包裹選取初始點(diǎn)x0，每次選擇最右手邊的一個點(diǎn)前進(jìn)可能的點(diǎn)都在n/m個凸包上在每個凸包內(nèi)部二分查詢：O(logm)時間復(fù)雜度選取最右點(diǎn)：O(n/m*logm)凸包上有M個點(diǎn)：O(m*n/m*logm)=O(nlogm)Chan’sAlgorithm求凸包的復(fù)雜度是O(nlogm)M是啥?Chan’sAlgorithm將求凸包過程記為Solve(N,M)假設(shè)最終凸包上的點(diǎn)數(shù)為H。從小到大枚舉M？O(nlog1)+O(nlog2)+…+O(nlogh)=O(n)*(log1+log2+…+logh)=O(n)*(log(h!))=O(n)*O(hlogh)=O(nhlogh)只要M>=H，算法就能正確出解Chan’sAlgorithm倍增枚舉M？M=2,4,8,16,…,2^t,…O(nlog2)+O(nlog4)+…+O(nlogh)=O(n)*(1+2+3+…+logh)=O(n)*O(log^2h)=O(nlog^2h)比指數(shù)更快的增長率M=2,4,16,256,…,2^(2^t))….O(nlog2)+O(nlog4)+…+O(nlogh)=O(n)*(1+2+4+..+logh)=O(n)*O(logh)

=O(nlogh)Minkowski和給定兩個點(diǎn)集P,Q，定義他們的Minkowski和P+Q={X1+X2,Y1+Y2|(x1,y1)∈P,(x2,y2)∈Q}給定點(diǎn)集P,Q,求他們Minkowski和的凸包面積|P|,|Q|<=10^5Minkowski和等價于P和Q凸包的Minkowski和凸包的邊構(gòu)成(Px+Py,P(x+1)+Py)or(Px+Py,Px+P(y+1))相當(dāng)于用P和Q凸包的所有邊做一個新凸包雙指針掃描解決PartII回顧：凸包增量法–O(n^2)Javris步進(jìn)法–O(nh)Graham掃描–O(nlogn)QuickHull–O(n^2)~O(n)Chan分塊法–O(nlogh)將凸包擴(kuò)展到三維情況。計算幾何基礎(chǔ)：表達(dá)定義直角坐標(biāo)系右手坐標(biāo)系三維空間的點(diǎn)坐標(biāo):(x,y,z)點(diǎn)和向量有什么區(qū)別Ax+By+Cz+D=0描述一個面(A,B,C)是平面的法向量右手法則描述一條直線基礎(chǔ)：兩個平面的交點(diǎn)(A1x+B1y+C1z+D1=0,A2x+B2y+C2z+D2=0)計算幾何基礎(chǔ)：表達(dá)直線：參數(shù)方程L={X0+tv}t∈RX0是L上的一個點(diǎn)V是一個向量，表示L的方向直線：兩點(diǎn)式(x-x0)/(x-x1)=(y-y0)/(y-y1)=(z-z0)/(z-z1)令v=P1-P0，則等價于上面的式子平面：點(diǎn)法式/標(biāo)準(zhǔn)式Ax+By+Cz+D=0<->A(x-x0)+B(y-y0)+C(z-z0)=0判定點(diǎn)和平面關(guān)系

Ax0+By0+Cz0+D>0->點(diǎn)與法向量同側(cè)計算幾何基礎(chǔ)：運(yùn)算點(diǎn)積<a,b>=AxBx+AyBy+AzBz<a,x>+<b,x>=<a+b,x><a,b>=|a|*|b|*cosθ<a,b>=0<->a⊥b也被稱為內(nèi)積(InnerProduct)計算幾何基礎(chǔ)：運(yùn)算P1：求一個點(diǎn)Q到直線(Po,V)的距離P0是直線上一點(diǎn)，v是方向向量直線上的點(diǎn)Q滿足Q=P0+λv，v∈RP2：求一個點(diǎn)Q到平面(Po,N)的距離P0是平面上一點(diǎn)，N是法向量第一個問題：如何判斷點(diǎn)X在不在平面上<X-P0,N>=0或者<X,N>=<P0,N>計算幾何基礎(chǔ)：運(yùn)算SolutiontoP1：這個方法也適用于2D。計算幾何基礎(chǔ)：運(yùn)算SolutiontoP2：假設(shè)q’是Q在π上的投影。計算幾何基礎(chǔ)：運(yùn)算P3：給定兩條異面直線，求它們之間的距離假設(shè)兩條直線是L1=P1+us,L2=P2+vt(s,t∈R)垂線交點(diǎn)是Q1=P1+us,Q2=P2+vt那么有<Q1-Q2,u>=0和<Q1-Q2,v>=0計算幾何基礎(chǔ)：運(yùn)算Ardenia給定三維空間上的兩條線段，求它們的最近距離。分情況討論(1)線段所在直線是異面/相交直線計算異面直線距離當(dāng)且僅當(dāng)兩個垂點(diǎn)都在線段上時取到(2)直線平行，或(1)的條件不滿足分別計算四個端點(diǎn)到另一條線段的最短距離視為平面問題StarWar給定三維空間上的兩個四面體，求它們的最近距離。保證四面體相離分情況討論點(diǎn)-面距離線-面距離？面-面距離？計算幾何基礎(chǔ)：運(yùn)算二維叉積a×b=AxBy-AyBxa×b=|a||b|sinθ三維叉積：定義c=a×b=|a||b|sinθ*nn是和ab所在平面垂直的單位向量a×b=-b×a也被稱為外積(OuterProduct)確定n的方向右手定則/右手系右手四指從X掃到Y(jié)，大拇指方向?yàn)镹計算幾何基礎(chǔ)：運(yùn)算平面上三個不共線點(diǎn)確定唯一平面。給定三個點(diǎn)M1,M2,M3，求平面解析式。N=(M2-M1)×(M3-M1)平面上的點(diǎn)P應(yīng)當(dāng)滿足<P-M1,N>=0計算幾何基礎(chǔ)：運(yùn)算計算P1(x1,y1,z1)×P2(x2,y2,z2)的值假設(shè)i=(1,0,0),j=(0,1,0),k=(0,0,1)P1×P2=(x1i+y1j+z1k)×(x2i+y2j+z2k)=x1x2(i×i)+x1y2(i×j)+x1z2(i×k)+y1x2(j×i)+y1y2(j×j)+y1z2(j×k)+z1x2(k×i)+z1y2(k×j)+z1z2(k×k)=(y1z2-y2z1)i+(z1x2-z2x1)j+(x1y2-x2y1)k每一項(xiàng)看起來都像一個二維叉積?；貞洠喝A行列式按第1行展開計算幾何基礎(chǔ)：運(yùn)算叉積的另一種寫法：三階行列式對上式進(jìn)行求值，可以得到相同的結(jié)果。計算幾何基礎(chǔ)：運(yùn)算2D：用a×b表示以a和b為邊的平行四邊形面積3D：|a×b|表示以a和b為邊的平行四邊形面積平行四邊形加一維就是平行六面體給定向量a,b,c，求以a,b,c為三邊的平行六面體體積計算幾何基礎(chǔ)：運(yùn)算求平行六面體的面積S(Base)=|b×c|H=|a|cosαΑ也是b×c和a的夾角V=SH=|a|*|b×c|*cosα=a·(b×c)a·(b×c)被稱為向量的混合積，記作[a,b,c]計算幾何基礎(chǔ)：運(yùn)算為什么叫[a,b,c]實(shí)質(zhì)是一個三階行列式[a,b,c]=|det(a,b,c)|混合積滿足輪換性，[a,b,c]=[b,c,a]=[c,a,b][a,b,c]=-[c,b,a]什么時候[a,b,c]>0?A,B,C成右手系如何求以a,b,c為邊的三棱錐體積？V(三棱錐)=1/6V(六面體)三維空間中的三棱錐也被稱為單純形ALetterToProgrammers給定一個向量，模擬以下操作(1)平移增量(x,y,z)(2)將向量放大到α倍(3)將向量沿指定的旋轉(zhuǎn)軸(x,y,z)逆時針旋轉(zhuǎn)d度(4)將之前的x個操作重復(fù)執(zhí)行y次序列長<=1000涉及數(shù)字除角度外均為整數(shù)且<1000構(gòu)造變換矩陣，進(jìn)行矩陣乘法聲明向量為(x,y,z,1)第四維的作用計算幾何基礎(chǔ)：變換放縮向量可以類似寫出計算幾何基礎(chǔ)：變換在二維平面上，一個向量逆時針旋轉(zhuǎn)α度A=((cosα,-sinα),(sinα,cosα))在三維平面上，一個向量繞z軸逆時針旋轉(zhuǎn)α度在三維平面上，一個向量繞x軸逆時針旋轉(zhuǎn)α度在三維平面上，一個向量繞y軸逆時針旋轉(zhuǎn)α度在三維平面上，一個向量先繞x旋轉(zhuǎn)α度，再按y旋轉(zhuǎn)β度，最后按z旋轉(zhuǎn)γ度計算幾何基礎(chǔ)：變換計算幾何基礎(chǔ)：變換符合題目要求的是第一個考慮原題，旋轉(zhuǎn)平面法向量將指定向量旋轉(zhuǎn)到z軸計算幾何基礎(chǔ)：變換(1)沿z軸，旋轉(zhuǎn)向量到xOz平面(2)沿y軸，旋轉(zhuǎn)向量到z軸上現(xiàn)在可以處理沿原點(diǎn)旋轉(zhuǎn)的情況了先將法向量旋轉(zhuǎn)到z軸，沿xOy平面旋轉(zhuǎn)角度，再把法向量轉(zhuǎn)回去計算幾何基礎(chǔ)：變換第二個矩陣是假設(shè)法向量為單位向量得到的解決原問題計算幾何基礎(chǔ)：變換先把平面移回原點(diǎn)(-a,-b,-c)，最后再移回去直線是(a,b,c)->(d,e,f)，方向(u,v,w)是單位向量將點(diǎn)(x,y,z)帶入，可以得到第二式凸包：定義和實(shí)現(xiàn)在三維空間上定義凸多面體(convexpolyhedron)對于形內(nèi)兩點(diǎn)X和Y，線段XY一定完全位于形內(nèi)對于多邊形的每個面，整個多邊形都在其一側(cè)…………如何存儲凸多面體？關(guān)鍵：存儲凸多邊形的面(facet)拆一條邊為兩條半邊見右面的環(huán)繞標(biāo)志所有平面法線向外Aerodynamics給定凸多面體S上的n個頂點(diǎn)，假設(shè)所有頂點(diǎn)的z坐標(biāo)最小為zmin最大為zmax，求S在z=zmin到z=zmax中每個整數(shù)平面上截取的面積。N<=100,x,y,z<=100且均為整數(shù).Aerodynamics需要計算三維凸包么對于[zmin,zmax]中的每個整數(shù)，計算所有邊在z=z’上的投影，計算凸包面積即可ShadeofHallelujahMountain給定凸多邊形S，一個投影平面P0和光源L求S在P0上造成陰影的體積大小簡單起見，保證平面和凸多邊形不相交。N<=100.平面旋轉(zhuǎn)后求凸包即可不用旋轉(zhuǎn)知識怎么做卷包裹法(Gift-Wrapping)回憶2D下的卷包裹法Expandto3D一張紙緊貼著凸包的一條邊AB沿AB的右手邊收攏，直到遇到頂點(diǎn)C為止那么ABC是凸包上的一個面下一個方向？遞歸：沿ac和cb方向搜索去遞歸拓展性：能不能拓展到高維度上卷包裹法(Gift-Wrapping)初始邊的選擇（見圖(a)）將點(diǎn)集投影到平面上求凸包，凸包的任一條邊均可時間復(fù)雜度O(nh)卷包裹法(Gift-Wrapping)voidwrap(inti,intj){intk=i,l,m;for(m=0;m<h;m++)if((I[m]==i&&J[m]==j)||(J[m]==i&&K[m]==j)||(K[m]==i&&I[m]==j))

return;for(l=0;l<n;l++)if(k==i||SignedVolume(P[i],P[j],P[k],P[l])>EPS)k=l;if(k==j)return;I[h]=i;J[h]=j;K[h]=k;h++;wrap(k,j);wrap(i,k);}增量法(Incremental)考慮在線版本的問題給定點(diǎn)集P，每次加入一個點(diǎn)，動態(tài)維護(hù)P的凸包。假設(shè)當(dāng)前凸包未退化（體積>0）(1)點(diǎn)P在凸包內(nèi)或凸包面上(2)點(diǎn)P在凸包外刪除不必要的凸包面將新點(diǎn)加入凸包判定面(a,b,c)對點(diǎn)P可見<P-a,N>>0N=(b-a)×(c-a)<P-a,(b-a)×(c-a)>>0->[p-a,b-a,c-a]>0增量法(Incremental)白色的面從Pr可見，灰色的面從Pr不可見黑色的邊被稱為地平線地平線的兩端，一定是一個可見面一個不可見面增量法(Incremental)刪除可見面用新點(diǎn)連接地平線的每一條邊初始化：得到一個非退化的三棱錐初始化失敗的情況增量法(Incremental)證明：凸多面體的邊數(shù)和面數(shù)是O(n)級別(1)由歐拉公式，F(xiàn)(面數(shù))+V(點(diǎn)數(shù))-E(邊數(shù))=2(2)一條邊恰歸屬于兩個面，一個面有>=3條邊，2E>=3F聯(lián)立(1)(2)可得E<=3V-6,F<=2V-4時間復(fù)雜度：O(n^2)查詢可見面和地平線可以用一個DFS統(tǒng)一解決拓展性：可以拓展到高維情況隨機(jī)增量(RandomizedIncremental)考慮增量算法的一個改進(jìn)尋找地平線時不枚舉所有面，而是利用之前的信息隨機(jī)增量(RandomizedIncremental)定義二分圖C=(P,F,E)如果一個點(diǎn)P看得到一個面F，在他們之間連邊得到的二分圖稱為沖突圖（conflictgraph）沖突圖的兩部分別是未處理的點(diǎn)和已存在的面查詢可見面

直接從沖突圖里面讀取設(shè)置點(diǎn)為已處理，刪除平面直接對二分圖進(jìn)行操作加入新面枚舉每個點(diǎn)，判斷可見性隨機(jī)增量(RandomizedIncremental)上圖是Conflictgraph的一個例子初始化：建立單純形，O(4n)建立初始沖突圖時間復(fù)雜度O(n^2)。隨機(jī)增量(RandomizedIncremental)時間復(fù)雜度瓶頸在于加入新facet時的處理。新的面一定連接當(dāng)前處理點(diǎn)Pr和一條地平線e假設(shè)e原先連接兩個面f1,f2（恰好有一個面將被剔除）證明：點(diǎn)Pt若能看見f，必定能看見f1或f2在加入facet時只需要考慮能見到f1/f2的點(diǎn)隨機(jī)增量(RandomizedIncremental)共面點(diǎn)處理：Pr對f可不可見？應(yīng)當(dāng)視為不可見，并合并兩個facet。時間復(fù)雜度分析整個過程中創(chuàng)建的facet個數(shù)是O(n)的算法的復(fù)雜度是O(nlogn)，證明較為繁復(fù)先略過參見ComputationalGeometry:AlgorithmsandApplications,Chapter11分治法(Divide-And-Conquer)推廣到3DO(n)合并兩個凸包需要一個頂點(diǎn)序考慮在C1和C2間設(shè)立平面H0頂點(diǎn)序是C1/C2邊界點(diǎn)間的連線在H0上的頂點(diǎn)序難想難寫，不推薦O(nlogn)QuickHull回憶2D下的QuickHullQuickHull(a,b)找到離ab最遠(yuǎn)的點(diǎn)c，那么c一定在凸包上QuickHull(a,c)QuickHull(c,b)3D情況：Quickhull(a,b,c)處理所有位于面a-b-c右側(cè)的點(diǎn)集凸包判定點(diǎn)集和法線同側(cè):[p-a,p-b,p-c]>0QuickHullQuickhull(P0,P1,P2)找到離平面(P0,P1,P2)最遠(yuǎn)的點(diǎn)K刪除在三棱錐K-P0-P1-P2內(nèi)的點(diǎn)和面Quickhull(K,P0,P1)Quickhull(K,P1,P2)Quickhull(K,P2,P0)紅色箭頭為各平面法線這個算法是有效的么？QuickHull問題在哪里？觀察點(diǎn)T的位置T同時在平面K-P0-P1和K-P2-P0外側(cè)一個點(diǎn)會被遞歸多次為什么2d下沒有這個問題？遞歸的各個集合有交集處理方式：隨意分配到一個集合內(nèi)TQuickHull證明：隨意分配可以保證算法正確性如果一個點(diǎn)是凸包上的點(diǎn)，那么永遠(yuǎn)不會被其他三棱錐包含而剔除因此隨意分配不會導(dǎo)致漏算等情況Quickhull(P0,P1,P2,S)找到離平面(P0,P1,P2)最遠(yuǎn)的點(diǎn)K刪除在三棱錐K-P0-P1-P2內(nèi)的點(diǎn)和面將S中剩下的點(diǎn)分到三個外集中Quickhull(K,P0,P1,S1)Quickhull(K,P1,P2,S2)Quickhull(K,P2,P0,S3)QuickHullinKDQuickhull拓展性很好，可以解決任意維凸包。(D-1)維平面被稱為凸包的facet，是凸包的組成部分。相當(dāng)于二維下的邊和三維下的面(D-2)維平面被稱為凸包的ridge，是兩個facet的交集。相當(dāng)于二維下的點(diǎn)和三維下的邊SimplifiedBeneath-BeyondTheorem若H是空間Rd上的一個凸包，P是H外一點(diǎn)，一個facetF是H+P的凸包當(dāng)且僅當(dāng)：(1)F∈H，P在F下方(2)F?H，且F由P和一個ridge組成，這個ridge關(guān)聯(lián)的一個facet在p下方，其他在p上方QuickHullinKD

初始化

尋找最遠(yuǎn)點(diǎn)

查詢地平線

創(chuàng)建facet

分配頂點(diǎn)

刪除可見面復(fù)雜度：O(nlogn)(d<=3),~O(n^(d/2))(d>=4)Chan’sAlgorithm回憶二維的Chan’sAlgorithmStep1：將點(diǎn)均分為N/M個部分對每個點(diǎn)集進(jìn)行Graham-Scan，得到N/M個凸包Step2：合并N/M個凸包卷包裹選取初始點(diǎn)x0，每次選擇最右手邊的一個點(diǎn)前進(jìn)在凸包上二分Chan’sAlgorithm能否擴(kuò)張到三維？Chan’sAlgorithmStep1Graham-Scan不能擴(kuò)展到三維三維中沒有非常良好的序用隨機(jī)增量/Quickhull代替，依然是O(nlogn)Step2卷包裹算法不能優(yōu)化到對每個凸包logm三維中沒有良好的點(diǎn)序給定一個多面體，在O(logn)時間內(nèi)得到卷包裹的下一個目標(biāo)給定一個凸點(diǎn)集，在O(logn)時間內(nèi)，找到點(diǎn)P使得面ABP和面ABC二面角最大Dobkin-KirkpatrickHierarchy對點(diǎn)集進(jìn)行D-K分層假設(shè)點(diǎn)集序列P0,P1,…,PkP0=P，是原凸多邊形Pi+1由Pi刪掉一個點(diǎn)集的獨(dú)立集得到刪掉的點(diǎn)中沒有連邊的Pk是一個單純形（三棱錐或四面體）Dobkin-KirkpatrickHierarchy以上是一次找刪除點(diǎn)集的操作可以證明這么做保證K最大為O(logn)級別Dobkin-KirkpatrickHierarchy查詢點(diǎn)集從Pk開始查詢，Pk的查詢是O(4)的每次退回Pi-1查詢，只查詢Pi-1中當(dāng)前結(jié)果的鄰居可以證明查詢的復(fù)雜度也是O(logn)Chan’sAlgorithm解決了點(diǎn)集查詢問題，剩下的步驟同以往時間復(fù)雜度是O(nlogh)Chan’sD-CAlgorithm基于2維分治法的3維凸包和上一個名字一樣，加上詞語以區(qū)別兩個算法的作者是同一個人TimothyM.Chan回憶2維分治法分別考慮上下凸殼Chan’sD-CAlgorithm將三維問題轉(zhuǎn)為二維問題考慮凸包的一個facet，所在的平面是z=sx+ty+b將t看成時間參數(shù)，定義t時刻的平面點(diǎn)集Pt=(x,z-ty)(1)點(diǎn)P在三維凸包的下凸殼上，當(dāng)且僅當(dāng)在某個時間t時，Pt落在直線y=sx+b上，且其他點(diǎn)在該直線上方(2)邊P1P2在三維凸包的下凸殼上，當(dāng)且僅當(dāng)某個時間t時，P1P2是二維凸殼的一條邊求t=-inf~+inf之間凸殼的動畫Chan’sD-CAlgorithm雖然時間t是無窮的，但凸包點(diǎn)集的變化次數(shù)有限(1)點(diǎn)Pj進(jìn)入凸包，刪除邊PiPk，加入PiPj/PjPk(2)點(diǎn)Pj離開凸包，刪除PiPj/PjPk，加入PiPk一個點(diǎn)進(jìn)入凸包一次離開凸包一次將點(diǎn)集按x排序，進(jìn)行分治Solve(l,r)Solve(l,mid)Solve(mid+1,r)合并兩段點(diǎn)集的動畫Chan’sD-CAlgorithm關(guān)鍵操作：合并點(diǎn)集L和R的凸殼動畫為A初始動畫：合并兩個t=-inf時的下凸包二維的凸包合并維護(hù)可能發(fā)生的增刪點(diǎn)事件(1)A和B的增刪點(diǎn)操作(2)切線u-v的改動(1)的維護(hù)如果L發(fā)生了增刪點(diǎn)，當(dāng)且僅當(dāng)涉及點(diǎn)在U左側(cè)時，A需要增刪對應(yīng)的點(diǎn)如果R發(fā)生了增刪點(diǎn)，當(dāng)且僅當(dāng)涉及點(diǎn)在V右側(cè)時，A需要增刪對應(yīng)的點(diǎn)以上兩個事件對應(yīng)的時刻由分治過程得到。Chan’sD-CAlgorithm(2)的維護(hù)U-V是切線的充要條件是(1)u-uv是逆時針，(2)uu+v是順時針，(3)uvv+是逆時針，(4)uv-v是順時針。(1)不滿足：新的切線是u-v，從u-和v之間刪除u(2)不滿足：新的切線是u+v，在u和v之間插入u+(3)不滿足：新的切線是uv+，在u和v+之間刪除v(4)不滿足：新的切線是uv-，在u和v之間插入v-Chan’sD-CAlgorithm(2)的維護(hù)計算事件發(fā)生的時間：三點(diǎn)共線復(fù)雜度O(nlogn)ImplementationChan’sD-CAlgorithmHull(a,b)：a用于存儲事件列表，b用于輔助Turn(a,b,c)返回三點(diǎn)是順時針還是逆時針假設(shè)此時last和next里存儲的是兩個t=-inf時的凸包Chan’sD-CAlgorithm合并凸殼的事件Chan’sD-CAlgorithm時光倒流在prev和next中存下點(diǎn)j進(jìn)入凸包時的鄰接點(diǎn)，以及t=-inf時的凸包用于返回上一層，以及輸出答案用Chan’sD-CAlgorithm輸出答案對返回的事件序列進(jìn)行模擬即可當(dāng)一個點(diǎn)j被插入凸包時，假設(shè)兩側(cè)節(jié)點(diǎn)是i和k存在時刻t使i,j,k共線，且其他頂點(diǎn)在直線上方I,j,k都在某個平面z=sx+ty+b上，且其他點(diǎn)在平面上方另一側(cè)凸包可以類似處理Chan’sD-CAlgorithm給定平面點(diǎn)集P，在線查詢離輸入點(diǎn)(a,b)最近的點(diǎn)。點(diǎn)距離用直線距離。Dist^2=(a-x)^2+(b-y)^2=(x^2+y^2)-2ax-2by+(a^2+b^2)A^2+B^2是常數(shù)，可以忽略在三維空間上定義點(diǎn)(X’,Y’)->(2X’,2Y’,X’^2+Y’^2)存儲分治中所有時刻的凸包點(diǎn)集，考慮時刻b的情況Chan’sD-CAlgorithm在時刻B，(x,z-by)=(2X’,X’^2+Y’^2-2BY’)而此時求的dist等于x’^2+y’^2-2ax’-2by’恰好等于新坐標(biāo)系中的-ax+y在新凸包上進(jìn)行二分即可PartIIConclusionO(n^2)卷包裹法–輸出敏感，實(shí)現(xiàn)簡單增量法–思路直觀O(nlogn)隨機(jī)增量–思路直觀，效果不錯，但較難實(shí)現(xiàn)D-C（分治法）–做法直觀，效率也很好，但較難實(shí)現(xiàn)QuickHull–擴(kuò)展性好，直接擴(kuò)展到高維Chan’sAlgorithm–輸出敏感，時間復(fù)雜度最優(yōu)，但實(shí)現(xiàn)非常困難，需要輔助的定位結(jié)構(gòu)Chan’sD-C–思路精巧，實(shí)現(xiàn)靈活，但效率較低重心P1：給定平面上的三角形，求其重心坐標(biāo)。幾何定義：頂點(diǎn)與對邊中點(diǎn)的連線交點(diǎn)為重心(Gx,Gy)=((Ax+Bx+Cx)/3,(Ay+By+Cy)/3)G=(A+B+C)/3P2：給定空間內(nèi)的三棱錐，求其重心坐標(biāo)。幾何定義：頂點(diǎn)和對面重心的連線交點(diǎn)為重心。G=(A+B+C+D)/4可以推廣到N維單純形上P3：給定平面內(nèi)的凸包，求凸包的重心坐標(biāo)。P4：給定空間內(nèi)的凸包，求凸包的重心坐標(biāo)。重心SolutiontoP3對凸包進(jìn)行三角剖分對于每個三角形，求出其面