同構(gòu)化二維點集凸殼算法研究.pdf

1、凸殼問題是計算幾何中最重要、最基本，也是得到大量深入研究，并有廣泛應用的問題之一。其應用領(lǐng)域包括統(tǒng)計學等。它是在20世紀提出的，70年代以來，二維凸殼所具有的問題復雜性與應用重要性，使國內(nèi)外專家學者對凸殼算法頗為關(guān)注，20世紀末期就已提出很多著名的凸殼算法，諸如卷包裹凸殼算法、格雷厄姆凸殼算法、折半分治凸殼算法，等等<'[5]>?？梢哉f凸殼算法研究始于70年代、盛于80年代、極于90年代；然而，進入21世紀以來，凸殼算法研究出現(xiàn)了停滯不

2、前的尷尬窘?jīng)r，所以有關(guān)凸殼的生成算法不是很多。在現(xiàn)有的凸殼算法里不但有串行并行之分，同時亦有“增點”遞推與“刪點”遞推之分。 本文在前人研究的基礎(chǔ)上，展開了基于同構(gòu)化基本原理新視角的點集凸殼算法(注：包括串行算法與并行算法；下同)研究。同構(gòu)化點集凸殼算法研究的主要內(nèi)容有： (1)現(xiàn)行點集凸殼算法反思研究，以發(fā)掘其弱點根源、借鑒其歷史經(jīng)驗； (2)點集凸殼的同構(gòu)化構(gòu)造特性研究，以尋求其同構(gòu)化構(gòu)造本質(zhì)； (3

3、)點集凸殼算法同構(gòu)化研究，以創(chuàng)出性能更優(yōu)的點集凸殼新算法。 在同構(gòu)化研究的基礎(chǔ)之上，本文提出了具有代表性的“動態(tài)基線最大傾角的凸殼新算法”、“雙域雙向水平傾角最小化圈繞凸殼新算法”、和“基于工作站機群的并行凸殼新算法”，并且利用任一電子商務的文檔，必定的能唯一標識它的特性——“文紋”，首次將凸殼技術(shù)運用于數(shù)字加密，提出了“基于文紋的數(shù)字加密技術(shù)”。 除了以上用途外，凸殼在“計算圖形、圖象處理、模式識別、指紋識別、地物辨識

4、、地質(zhì)勘探、網(wǎng)點布局、環(huán)境監(jiān)測、……”中，均有廣泛而重要的學術(shù)意義與應用價值。例如：圖象處理中，可用尋求圖像凸殼，找到數(shù)字圖象中的關(guān)鍵凸面；古繁體文字分解中，可以構(gòu)造字形凸包，形成對文字的最優(yōu)劃分；模式識別中，可借模式凸殼，描述模式外形的重要特征；物體分類中，可憑各物體凸殼相似度，勾畫出這些物體所屬類別；計算機圖形學中，可用一組點的凸殼，顯示出其點簇：在指紋識別中，可以根據(jù)指紋邊緣輪廓點集凸殼，獲得高質(zhì)量的指紋，所以說凸殼的應用范圍非常