一種平面點集的高效凸包算法
發(fā)布時間：2018-08-21 09:31
【摘要】：凸包問題是計算幾何的基本問題之一。為實時計算平面點集的凸包,近年來許多學者提出很多優(yōu)秀的算法,但依然不能滿足實際中的實時性需求。為此,本文提出一種簡單但高效快速的凸包算法。由于凸包點必然位于平面點集邊緣,本文算法能夠快速地篩選出極少量的凸包點候選點集,這是本算法的核心優(yōu)勢。然后,使用本文另外提出的一種簡單易于實現(xiàn)的改進的Graham掃描算法,或其他任何已有的凸包檢測方法,即可快速而準確地計算出點集的凸包。經(jīng)典的Graham掃描算法使用一個基點計算凸包,本文的改進算法則是根據(jù)凸包候選點的分布情況,將點集分成4個子塊,也即使用4個基點分別在每塊中進行凸包檢測,最后將每個子塊中的檢測結果進行合并,得到最終的完整凸包。實驗中,采用一組公開的動物骨骼點云數(shù)據(jù)作為一次測試集。在凸包計算完全正確的情況下,當點數(shù)約為3×1 0~5左右時,本算法的計算時間比其他算法減少2.22倍;當點數(shù)約為3×10~6時,本算法的計算時間比其他方法減少5.42倍。點數(shù)越多,所提出算法就表現(xiàn)出越明顯的優(yōu)勢。
[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.
【作者單位】： 四川大學電氣信息學院;
【基金】：國家自然科學基金資助項目(NSFC61473198)
【分類號】：O18
本文編號：2195290
[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.
【作者單位】： 四川大學電氣信息學院;
【基金】：國家自然科學基金資助項目(NSFC61473198)
【分類號】：O18
【相似文獻】
相關期刊論文 前10條
1 鄒中柱;;凸函數(shù)類凸包中函數(shù)星形性的半徑[J];湖南師范大學自然科學學報;1989年02期
2 宋麗;姜旭東;;卷包裹法求凸包問題算法分析與程序實現(xiàn)[J];牡丹江師范學院學報(自然科學版);2005年04期
3 呂偉,梁友棟;一般歐氏空間點集凸包的快速實時算法[J];應用數(shù)學學報;1992年02期
4 穆玉杰;平面有限點集凸包的計算機構造[J];西北大學學報(自然科學版);1982年02期
5 李杰民;;函數(shù)的凸包及其模擬方法[J];中國科技信息;2007年10期
6 徐宗本,張講社;N維點集凸包的計算機生成原理與方法[J];高校應用數(shù)學學報A輯(中文版);1991年03期
7 雷英果;多元凸包函數(shù)Lip連續(xù)性[J];福州大學學報(自然科學版);1993年01期
8 劉斌;王濤;;一種高效的平面點集凸包遞歸算法[J];自動化學報;2012年08期
9 于憲偉;B-凸包的內(nèi)部結構[J];錦州師范學院學報(自然科學版);2002年04期
10 張小朋;武芳;孟巖斌;張景輝;;一種利用凸包思想顧及障礙物的聚類分析[J];測繪科學技術學報;2008年02期
相關博士學位論文 前1條
1 Daoussa Daniel;完全交曲面陳示性數(shù)的凸包[D];華東師范大學;2015年
，本文編號：2195290
本文鏈接：http://www.sikaile.net/kejilunwen/yysx/2195290.html
最近更新
教材專著
