欢迎来到天天文库
浏览记录
ID:19212163
大小:2.65 MB
页数:10页
时间:2018-09-22
《一种平面点集高效凸包算法》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、一种平面点集的高效凸包算法刘凯1,夏苗1,杨晓梅1*(1.四川大学电气信息学院,四川成都610065)摘要:凸包问题是计算几何的基本问题之一。为了实时计算平面点集的凸包,近年来许多学者提出了很多优秀的算法,但依然不能满足实际中的实时性需求,因此,本文提出了一种简单但高效快速的凸包算法。根据凸包点的定义,凸包点必然位于平面点集的边缘;本算法根据凸包点的定义,能够快速地筛选出极少量的凸包点的候选点集,这是本算法的核心优势。然后,使用本文另外提出的一种简单易于实现的改进的Graham扫描算法,或者使用其他任何已有的凸包检测方法,就能够十分快速而准确地计算出点集的凸包。经典的Graham扫描算法使用
2、一个基点来计算凸包,所提出的改进的算法则是根据凸包候选点的分布情况,将点集分成四个子块,也就是使用四个基点分别在每块中进行凸包检测,最后将每个子块中的检测结果进行合并,得到最终的完整凸包。实验中,采用一组公开的动物骨骼点云数据作为一次测试集。在凸包计算完全正确的情况下,当点数约为30万左右时,本算法的计算时间比其他算法减少2.22倍;当点数约为300万个点时,本算法的计算时间减少比其他方法减少5.42倍。点数越多,所提出算法就表现出越明显的优势。关键词:凸包,预处理算法,改进的Graham扫描算法,平面点集中图分类号:TP311.1AnEffective2DConvexHullAlgorit
3、hmKaiLiu1,MiaoXia1,XiaomeiYang1*(1.SchoolofElectronicEngineeringandInformation,SichuanUniv.,Chengdu610065)Abstract:Convexhullisoneoftheessentialissuesincomputationalgeometricofplanarpointsset.Traditionalconvexhullmethodscannotmeettheincreasingdemandthatlargemountsofpointsmustbeprocessedwithinashort
4、timeinpracticalengineering.Therefore,asimplebuteffectiveandtime-savingapproachcombinedofapreconditioningalgorithmandaconvexhullbuildalgorithmisproposedbythispaper.Accordingtothedefinitionofconvexhull,thekeypointsofconvexhullmustlocateontheborderoftheplanarpointsset.Soatinynumberofthesespecialpoints
5、canbefoundoutthroughthepreconditioningalgorithmonthebasesoftheconvexhulldefinition.Furthermore,thepreconditioningalgorithmisthecorealgorithmofthisarticle.Afterthepreprocessingprocedure,animprovedGrahamconvexhullbuildingalgorithmwhichissimplebuteasilytobeachievedisappliedtocalculatethefinalconvexhul
6、laccuratelyandeffectively,oranyotherconvexhullmethodscanbeadopted.TraditionalGrahamscanalgorithmbuildsconvexhullwithonebasepoint,whiletheimprovedGrahamscanalgorithmdividesthepointssetintofoursubpartsandgeneratesfourbasepoints.Thesefourbasepointsareusedtobuildthesub-convexhullinitsownsubpart.Asaresu
7、lt,anintegratedconvexhullisgeneratedfromthefoursub-convexhulls.Anexperimentemployingagroupofpublicanimalskeletons,provedthatcomparedwithtraditionalmethods,thetimecouldbereducedatleast2.22timesbyouralgorithm
此文档下载收益归作者所有