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

Ax0+By0+Cz0+D>0->點與法向量同側(cè)計算幾何基礎：運算點積<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)計算幾何基礎：運算P1：求一個點Q到直線(Po,V)的距離P0是直線上一點，v是方向向量直線上的點Q滿足Q=P0+λv，v∈RP2：求一個點Q到平面(Po,N)的距離P0是平面上一點，N是法向量第一個問題：如何判斷點X在不在平面上<X-P0,N>=0或者<X,N>=<P0,N>計算幾何基礎：運算SolutiontoP1：這個方法也適用于2D。計算幾何基礎：運算SolutiontoP2：假設q’是Q在π上的投影。計算幾何基礎：運算P3：給定兩條異面直線，求它們之間的距離假設兩條直線是L1=P1+us,L2=P2+vt(s,t∈R)垂線交點是Q1=P1+us,Q2=P2+vt那么有<Q1-Q2,u>=0和<Q1-Q2,v>=0計算幾何基礎：運算Ardenia給定三維空間上的兩條線段，求它們的最近距離。分情況討論(1)線段所在直線是異面/相交直線計算異面直線距離當且僅當兩個垂點都在線段上時取到(2)直線平行，或(1)的條件不滿足分別計算四個端點到另一條線段的最短距離視為平面問題StarWar給定三維空間上的兩個四面體，求它們的最近距離。保證四面體相離分情況討論點-面距離線-面距離？面-面距離？計算幾何基礎：運算二維叉積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é)，大拇指方向為N計算幾何基礎：運算平面上三個不共線點確定唯一平面。給定三個點M1,M2,M3，求平面解析式。N=(M2-M1)×(M3-M1)平面上的點P應當滿足<P-M1,N>=0計算幾何基礎：運算計算P1(x1,y1,z1)×P2(x2,y2,z2)的值假設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每一項看起來都像一個二維叉積?；貞洠喝A行列式按第1行展開計算幾何基礎：運算叉積的另一種寫法：三階行列式對上式進行求值，可以得到相同的結(jié)果。計算幾何基礎：運算2D：用a×b表示以a和b為邊的平行四邊形面積3D：|a×b|表示以a和b為邊的平行四邊形面積平行四邊形加一維就是平行六面體給定向量a,b,c，求以a,b,c為三邊的平行六面體體積計算幾何基礎：運算求平行六面體的面積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]計算幾何基礎：運算為什么叫[a,b,c]實質(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個操作重復執(zhí)行y次序列長<=1000涉及數(shù)字除角度外均為整數(shù)且<1000構(gòu)造變換矩陣，進行矩陣乘法聲明向量為(x,y,z,1)第四維的作用計算幾何基礎：變換放縮向量可以類似寫出計算幾何基礎：變換在二維平面上，一個向量逆時針旋轉(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)γ度計算幾何基礎：變換計算幾何基礎：變換符合題目要求的是第一個考慮原題，旋轉(zhuǎn)平面法向量將指定向量旋轉(zhuǎn)到z軸計算幾何基礎：變換(1)沿z軸，旋轉(zhuǎn)向量到xOz平面(2)沿y軸，旋轉(zhuǎn)向量到z軸上現(xiàn)在可以處理沿原點旋轉(zhuǎn)的情況了先將法向量旋轉(zhuǎn)到z軸，沿xOy平面旋轉(zhuǎn)角度，再把法向量轉(zhuǎn)回去計算幾何基礎：變換第二個矩陣是假設法向量為單位向量得到的解決原問題計算幾何基礎：變換先把平面移回原點(-a,-b,-c)，最后再移回去直線是(a,b,c)->(d,e,f)，方向(u,v,w)是單位向量將點(x,y,z)帶入，可以得到第二式凸包：定義和實現(xiàn)在三維空間上定義凸多面體(convexpolyhedron)對于形內(nèi)兩點X和Y，線段XY一定完全位于形內(nèi)對于多邊形的每個面，整個多邊形都在其一側(cè)…………如何存儲凸多面體？關鍵：存儲凸多邊形的面(facet)拆一條邊為兩條半邊見右面的環(huán)繞標志所有平面法線向外Aerodynamics給定凸多面體S上的n個頂點，假設所有頂點的z坐標最小為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的右手邊收攏，直到遇到頂點C為止那么ABC是凸包上的一個面下一個方向？遞歸：沿ac和cb方向搜索去遞歸拓展性：能不能拓展到高維度上卷包裹法(Gift-Wrapping)初始邊的選擇（見圖(a)）將點集投影到平面上求凸包，凸包的任一條邊均可時間復雜度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)考慮在線版本的問題給定點集P，每次加入一個點，動態(tài)維護P的凸包。假設當前凸包未退化（體積>0）(1)點P在凸包內(nèi)或凸包面上(2)點P在凸包外刪除不必要的凸包面將新點加入凸包判定面(a,b,c)對點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)刪除可見面用新點連接地平線的每一條邊初始化：得到一個非退化的三棱錐初始化失敗的情況增量法(Incremental)證明：凸多面體的邊數(shù)和面數(shù)是O(n)級別(1)由歐拉公式，F(xiàn)(面數(shù))+V(點數(shù))-E(邊數(shù))=2(2)一條邊恰歸屬于兩個面，一個面有>=3條邊，2E>=3F聯(lián)立(1)(2)可得E<=3V-6,F<=2V-4時間復雜度：O(n^2)查詢可見面和地平線可以用一個DFS統(tǒng)一解決拓展性：可以拓展到高維情況隨機增量(RandomizedIncremental)考慮增量算法的一個改進尋找地平線時不枚舉所有面，而是利用之前的信息隨機增量(RandomizedIncremental)定義二分圖C=(P,F,E)如果一個點P看得到一個面F，在他們之間連邊得到的二分圖稱為沖突圖（conflictgraph）沖突圖的兩部分別是未處理的點和已存在的面查詢可見面

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

初始化

尋找最遠點

查詢地平線

創(chuàng)建facet

分配頂點

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