凸殼算法及其應(yīng)用研究.pdf

1、凸殼在模式識(shí)別、圖象處理、圖形學(xué)和人工智能等方面有廣泛的應(yīng)用，許多實(shí)際問(wèn)題都可以歸納成凸殼問(wèn)題求解。對(duì)凸殼和凸殼直徑計(jì)算進(jìn)行了研究，提出了相關(guān)算法，同時(shí)對(duì)凸殼在輪廓匹配和高密度點(diǎn)集物碰撞檢測(cè)中的應(yīng)用進(jìn)行了探討，理論分析和實(shí)驗(yàn)結(jié)果驗(yàn)證算法的可行性和有效性。工作主要從以下六個(gè)方面展開： (1) 實(shí)時(shí)凸殼算法。 由于正切線算法計(jì)算凸殼時(shí)對(duì)新加入實(shí)時(shí)點(diǎn)進(jìn)行編號(hào)的局限性，提出一種實(shí)時(shí)凸殼算法。算法通過(guò)極值點(diǎn)將平面劃分為若干區(qū)域，根

2、據(jù)實(shí)時(shí)點(diǎn)所在區(qū)域，確定受影響的單調(diào)段，對(duì)受影響單調(diào)段上的頂點(diǎn)通過(guò)正切線算法重新計(jì)算，以橫坐標(biāo)作為新加入點(diǎn)的編號(hào)實(shí)現(xiàn)自動(dòng)編號(hào)，最終由新的單調(diào)段得到新的凸殼。 (2) 給定平面點(diǎn)集凸殼算法。 將正切線算法應(yīng)用到給定平面點(diǎn)集凸殼的計(jì)算中，通過(guò)凸殼的極值點(diǎn)定義了凸殼的單調(diào)段，并將點(diǎn)集分成若干個(gè)區(qū)域，對(duì)于點(diǎn)集中的點(diǎn)，若該點(diǎn)落在由各單調(diào)段所圍成的區(qū)域內(nèi)部，則該點(diǎn)一定不是凸殼上的點(diǎn)；計(jì)算落于其它區(qū)域中的點(diǎn)，只需通過(guò)該點(diǎn)與它所在區(qū)域的原

3、單調(diào)段進(jìn)行計(jì)算得到新單調(diào)段，從而得到給定平面點(diǎn)集的凸殼。 (3) 基于凸多邊形頂點(diǎn)間距離性質(zhì)的凸多邊形直徑算法。 平面點(diǎn)集的直徑問(wèn)題可以轉(zhuǎn)化為求凸多邊形直徑問(wèn)題，論文研究了凸多邊形的直徑計(jì)算，得出凸多邊形上頂點(diǎn)間距離關(guān)系的一些性質(zhì)，提出一種基于頂點(diǎn)間距離性質(zhì)的凸多邊形直徑算法，利用這些性質(zhì)可減少大量夾角符號(hào)計(jì)算。 (4) 基于凸多邊形頂點(diǎn)序列到邊的距離單調(diào)性的凸多邊形直徑算法。 研究了凸多邊形頂點(diǎn)序列到邊

4、的距離單調(diào)性，算法根據(jù)這種單調(diào)性通過(guò)折半查找實(shí)現(xiàn)對(duì)首個(gè)對(duì)跖點(diǎn)對(duì)的查找，實(shí)現(xiàn)了一種快速的凸多邊形直徑算法。 (5) 凸殼在輪廓匹配中的應(yīng)用研究。 輪廓匹配是計(jì)算機(jī)視覺(jué)研究中的一個(gè)重要課題，論文研究了平移旋轉(zhuǎn)和伸縮變換下的輪廓匹配問(wèn)題，得出了重心是平移旋轉(zhuǎn)和伸縮變換下的不變量，根據(jù)重心這一不變量計(jì)算變換中的平移量、旋轉(zhuǎn)角度和縮放因子，實(shí)現(xiàn)輪廓匹配。 (6) 凸殼在高密度點(diǎn)集物碰撞檢測(cè)中的應(yīng)用研究。 虛擬環(huán)境已

5、成為計(jì)算機(jī)科學(xué)的一個(gè)重要研究領(lǐng)域，虛擬對(duì)象之間的碰撞檢測(cè)是其關(guān)鍵問(wèn)題之一。論文對(duì)二維平面對(duì)象碰撞檢測(cè)問(wèn)題進(jìn)行研究，將凸殼應(yīng)用到高密度點(diǎn)集物碰撞檢測(cè)中，提出了一種基于凸殼包圍盒的高密度點(diǎn)集物碰撞檢測(cè)算法。首先計(jì)算待碰撞點(diǎn)集物的凸殼，通過(guò)對(duì)凸殼進(jìn)行求交運(yùn)算，若不相交，兩點(diǎn)集物未發(fā)生碰撞；若相交，在兩凸殼的交集區(qū)域中尋找碰撞點(diǎn)集。 算法取得了如下研究結(jié)果： (1) 實(shí)時(shí)凸殼算法實(shí)現(xiàn)了對(duì)實(shí)時(shí)點(diǎn)的自動(dòng)編號(hào)，對(duì)每一個(gè)新增實(shí)時(shí)點(diǎn)最多只

6、需對(duì)2個(gè)單調(diào)段進(jìn)行計(jì)算，提高了運(yùn)算效率。 (2) 對(duì)靜態(tài)凸殼的計(jì)算，落于由各單調(diào)段所圍成的區(qū)域外的點(diǎn)，只需跟該點(diǎn)所在區(qū)域的原單調(diào)段上的頂點(diǎn)進(jìn)行計(jì)算，減少了處理的點(diǎn)，提高了算法執(zhí)行速度。 (3) 利用頂點(diǎn)間距離關(guān)系的性質(zhì)提高了夾角符號(hào)序列法的計(jì)算速度，空間復(fù)雜度為O(n)，存儲(chǔ)效率高。 (4) 查找首個(gè)對(duì)跖點(diǎn)對(duì)所需時(shí)間復(fù)雜度為O(logn)，整個(gè)算法所需輔助空間為常量，時(shí)間和空間兩方面都優(yōu)于同類算法，該算法效率高、