凸殼演算法代碼

① 王曉東的人物簡介

職稱 教授
職務 博士生導師
主講課程 演算法與數據結構、演算法設計與分析、文獻閱讀與選題報告
研究方向 計算機演算法設計與演算法評價、並行和分布式演算法設計、計算復雜性理論等
1998年任福州大學計算機系主任。2003年任福州大學數學與計算機學院院長、博士生導師。2007年8月起任泉州師范學院副院長(副廳)。現任福建省計算機學會理事長、中國計算機學會理事、福州大學一級責任教授、福州大學計算機應用技術省重點學科學科帶頭人。先後主持了國家自然科學基金項目、國家優秀留學回國人員基金項目、福建省傑出人才基金項目和省自然科學基金項目等8個研究課題，獲得國家科技進步二等獎1項，省科技進步二等獎3項；主持國家精品課程演算法與數據結構和演算法設計與分析的課程建設。2008年被評為福建省教學名師，獲福建省教學成果一等獎等。在國內外重要學術刊物上發表有創見性的論文50餘篇；在演算法復雜性研究方面取得了一系列理論研究和應用成果。例如，在對著名的凸殼問題的計算復雜性研究成果中推廣了關於判定樹模型下問題的計算復雜性下界著名的Ben-Or定理，並應用於分析凸殼問題的計算復雜性，在較一般的情況下改進和完善了國際演算法界知名學者Aggarwal，Steele和Yao等提出的關於凸殼問題計算復雜性下界的結果，研究成果得到同行專家的好評並被國內權威刊物所引用。正式出版與演算法設計與分析、數據結構相關的學術著作和教材11部，其中4部為普通高等教育「十一五」國家級規劃教材，《演算法設計與分析》被國內多所大學和科研機構列為博、碩士生入學考試指定教材。

② 周培德演算法

平面點集三角剖分的周培德演算法是周培德於1996提出的(周培德，1996，2000)，該演算法首先對點集逐層求凸包，如圖3.8(a)所示為需要剖分的點集，圖3.8(b)為對點集逐層求凸包，對點集逐層求凸包時可能存在1個或2個孤立點無法組成凸包，此時恰好沒有剩下孤立的點;然後將兩兩凸包之間的環狀區域分割成三角形，最後調整相鄰環域的三角剖分便能獲得最小權的三角剖分，如圖3.8(c)為從內到外將凸包之間的環狀區域分割成三角形，圖3.8(d)為點集的三角剖分結果。

第十三步:對以C_m中的邊(或已變動的邊)為共用邊的三角形對，採用第十二步的方法檢查是否需要改變原有的三角剖分。然後，沿C_m-1，…，C₂的各條邊(或已變動的邊)尋找兩個有共用邊的三角形對，並用第十二步的方法檢查是否需要改變原來的三角剖分，直到所有凸殼的邊檢查完為止。

③ 貪心演算法

平面點集三角剖分的貪心演算法要求三角剖分後邊的總長度盡可能小。演算法的基本思想是將所有的兩點間距離從小到大排序，依次序每次取一條三角剖分的邊，直至達到要求的邊數。以下是兩種貪心演算法的主要步驟。

3.2.2.1 貪心演算法1

第一步:設置一個記錄三角剖分中邊的數組T。

第二步:計算點集S中所有點對之間的距離d(p_i，p_j)，1≤i，j≤n，i≠j，並且對距離從小到大進行排序，設為d₁，d₂，…，d_n(n-1)/2，相應的線段記為e₁，e₂，…，e_n(n-1)/2，將這些線段存儲在數組E中。

第三步:從線段集E中取出長度最短的邊e₁存到T中作為三角剖分的第一條邊，此時k=1。

第四步:依次從E中取出長度最短的邊e_k，與T中已有的邊進行求交運算，如果不相交則存到T中，並從E中刪除e_k。這一步運行到S中沒有邊為止，即至k=n(n-1)/2。

第五步:輸出T。

該演算法中，第二步需要計算n(n-1)/2次距離，另外距離排序需要O(n²lgn)次比較。T中元素隨第四步循環次數的增加而增加，因此向T中加入一條新邊所需要的判定兩條線段是否相交的次數也隨之增加。如果第四步的前3n-6次循環後已經構成點集的三角剖分，那麼第四步循環所需要的判定兩條線段是否相交的次數為

1+2+…+3n-7+(3n-6)×(n(n-1)/2-(3n-6))=O(n³)

在常數時間內可以判定兩條線段是否相交，因此該演算法的時間復雜性為O(n³)。

3.2.2.2 貪心演算法2

第一步:求點集的凸殼，設凸殼頂點為p₁，p₂，…，p_m，凸殼的邊為e₁，e₂，…，e_m。並將凸殼頂點按順序連接成邊的e_i加入T(三角剖分的邊集合)，並且e_i的權值被賦為1。凸殼內點的集合為S₁={p_m+1，p_m+2，…，p_n}。

第二步:從內部點S₁中任取一點p_i，求與p_i距離最近的點p_j，將線段 存入T。

第三步:求與p_j距離最近的點(除點p_i外)，設為p_k，並將線段 加入T，並將這些邊的權值設為1，而w_ij、w_jk和w_ki的值加1，即為2。邊的權值為2則表示該邊為兩個三角形共有。

第五步:對權值為1的邊(除e₁，e₂，…，e_m外)的兩個端點分別求與其距離最近的點，並將其連線(得到新的三角形)加入T，新三角形邊的權值加1。

第六步:對權值為1的邊重復上一步，當一條邊被使用一次其權值增加1，直到所有邊的權值均為2為止(除e₁，e₂，…，e_m外)。

貪心演算法2中，第一步耗費O(nlgn);第二步需要計算n-1次距離與n-2次比較;第三步求p_k要計算n-2次的距離與n-3次比較;第四步要進行(n-3)×3次的距離計算及(n-4)×3次比較;第五步至多進行n-6次的距離計算與n-7次比較;第六步到第五步的循環次數不超過3n-9;因此整個貪心演算法2的時間復雜性為

O(nlgn)+O(n)+O(n)+O(n)+(n-6)×(3n-9)=O(n²)