發(fā)布時(shí)間：2018-08-21 09:31

【摘要】：凸包問(wèn)題是計(jì)算幾何的基本問(wèn)題之一。為實(shí)時(shí)計(jì)算平面點(diǎn)集的凸包,近年來(lái)許多學(xué)者提出很多優(yōu)秀的算法,但依然不能滿足實(shí)際中的實(shí)時(shí)性需求。為此,本文提出一種簡(jiǎn)單但高效快速的凸包算法。由于凸包點(diǎn)必然位于平面點(diǎn)集邊緣,本文算法能夠快速地篩選出極少量的凸包點(diǎn)候選點(diǎn)集,這是本算法的核心優(yōu)勢(shì)。然后,使用本文另外提出的一種簡(jiǎn)單易于實(shí)現(xiàn)的改進(jìn)的Graham掃描算法,或其他任何已有的凸包檢測(cè)方法,即可快速而準(zhǔn)確地計(jì)算出點(diǎn)集的凸包。經(jīng)典的Graham掃描算法使用一個(gè)基點(diǎn)計(jì)算凸包,本文的改進(jìn)算法則是根據(jù)凸包候選點(diǎn)的分布情況,將點(diǎn)集分成4個(gè)子塊,也即使用4個(gè)基點(diǎn)分別在每塊中進(jìn)行凸包檢測(cè),最后將每個(gè)子塊中的檢測(cè)結(jié)果進(jìn)行合并,得到最終的完整凸包。實(shí)驗(yàn)中,采用一組公開(kāi)的動(dòng)物骨骼點(diǎn)云數(shù)據(jù)作為一次測(cè)試集。在凸包計(jì)算完全正確的情況下,當(dāng)點(diǎn)數(shù)約為3×1 0~5左右時(shí),本算法的計(jì)算時(shí)間比其他算法減少2.22倍;當(dāng)點(diǎn)數(shù)約為3×10~6時(shí),本算法的計(jì)算時(shí)間比其他方法減少5.42倍。點(diǎn)數(shù)越多,所提出算法就表現(xiàn)出越明顯的優(yōu)勢(shì)。
[Abstract]:Convex hull problem is one of the basic problems in computational geometry. In order to compute the convex hull of the plane point set in real time, many scholars have proposed many excellent algorithms in recent years, but they still can not meet the real time requirement in practice. Therefore, this paper presents a simple but efficient and fast convex hull algorithm. Because convex hull points must be located at the edge of the plane point set, this algorithm can quickly filter out a few candidate point sets of convex hull points, which is the core advantage of this algorithm. Then, using a simple and easy to implement improved Graham scan algorithm, or any other existing convex hull detection method, the convex hull of the point set can be calculated quickly and accurately. The classical Graham scan algorithm uses one basis point to calculate convex hull. The improved algorithm is to divide the point set into four sub-blocks according to the distribution of convex hull candidate points, that is, to detect convex hull in each block using four basis points. Finally, the detection results in each subblock are merged to obtain the final complete convex hull. In the experiment, a set of published animal bone point cloud data was used as a test set. When the computation of convex hull is correct, the computation time of this algorithm is 2.22 times less than that of other algorithms when the number of points is about 3 脳 10 ~ 5, and 5.42 times less than that of other methods when the number of points is about 3 脳 10 ~ 6. The more the number of points, the more obvious the advantages of the proposed algorithm.
【作者單位】： 四川大學(xué)電氣信息學(xué)院;
【基金】：國(guó)家自然科學(xué)基金資助項(xiàng)目(NSFC61473198)
【分類號(hào)】：O18

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 鄒中柱;;凸函數(shù)類凸包中函數(shù)星形性的半徑[J];湖南師范大學(xué)自然科學(xué)學(xué)報(bào);1989年02期

2 宋麗;姜旭東;;卷包裹法求凸包問(wèn)題算法分析與程序?qū)崿F(xiàn)[J];牡丹江師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2005年04期

3 呂偉,梁友棟;一般歐氏空間點(diǎn)集凸包的快速實(shí)時(shí)算法[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);1992年02期

4 穆玉杰;平面有限點(diǎn)集凸包的計(jì)算機(jī)構(gòu)造[J];西北大學(xué)學(xué)報(bào)(自然科學(xué)版);1982年02期

5 李杰民;;函數(shù)的凸包及其模擬方法[J];中國(guó)科技信息;2007年10期

6 徐宗本,張講社;N維點(diǎn)集凸包的計(jì)算機(jī)生成原理與方法[J];高校應(yīng)用數(shù)學(xué)學(xué)報(bào)A輯(中文版);1991年03期

7 雷英果;多元凸包函數(shù)Lip連續(xù)性[J];福州大學(xué)學(xué)報(bào)(自然科學(xué)版);1993年01期

8 劉斌;王濤;;一種高效的平面點(diǎn)集凸包遞歸算法[J];自動(dòng)化學(xué)報(bào);2012年08期

9 于憲偉;B-凸包的內(nèi)部結(jié)構(gòu)[J];錦州師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2002年04期

10 張小朋;武芳;孟巖斌;張景輝;;一種利用凸包思想顧及障礙物的聚類分析[J];測(cè)繪科學(xué)技術(shù)學(xué)報(bào);2008年02期

相關(guān)博士學(xué)位論文 前1條

1 Daoussa Daniel;完全交曲面陳示性數(shù)的凸包[D];華東師范大學(xué);2015年

，

本文編號(hào)：2195290