一种平面点集的高效凸包算法
|
摘要
凸包问题是计算几何的基本问题之一。为实时计算平面点集的凸包,近年来许多学者提出很多优秀的算法,但依然不能满足实际中的实时性需求。为此,本文提出一种简单但高效快速的凸包算法。由于凸包点必然位于平面点集边缘,本文算法能够快速地筛选出极少量的凸包点候选点集,这是本算法的核心优势。然后,使用本文另外提出的一种简单易于实现的改进的Graham扫描算法,或其他任何已有的凸包检测方法,即可快速而准确地计算出点集的凸包。经典的Graham扫描算法使用一个基点计算凸包,本文的改进算法则是根据凸包候选点的分布情况,将点集分成4个子块,也即使用4个基点分别在每块中进行凸包检测,最后将每个子块中的检测结果进行合并,得到最终的完整凸包。实验中,采用一组公开的动物骨骼点云数据作为一次测试集。在凸包计算完全正确的情况下,当点数约为3×1 0~5左右时,本算法的计算时间比其他算法减少2.22倍;当点数约为3×10~6时,本算法的计算时间比其他方法减少5.42倍。点数越多,所提出算法就表现出越明显的优势。
Convex hull is one of the essential issues in computational geometric of planar points set.In recent years,many scholars have put forward many excellent algorithms to calculate the convex hull of the plane point set in real time,which,however,still can not satisfy the practical real-time demand.To this end,a simple but efficient and fast convex hull algorithm is proposed in this paper.Due to the fact that the convex hull points must be located at the edge of the planar point set,the algorithm in this paper can quickly find out the few candidate points of the convex wrapping point,which is the core advantage of this algorithm.Then,by using a simple and effectively-improved Graham scan algorithm which is also put forward by this paper,or any other existing convex hull methods,the points set of the convex hull can be calculated quickly and accurately.Conventional Graham scan algorithm calculate convex hull with one basis point.Based on the convex hull of distribution of candidate points set,the improved algorithm of this paper divides basis points into four subsystems,namely 4 basis points are tested respectively in each part,then mergers all the test results of each parts,and finally gets the complete convex hull.In the experiment,a set of public animals bone points clouds were used.The convex hull calculation is perfectly correct,but the calculation time of this algorithm is 2.22 times less than that of other algorithms when the number of points is about 3 ×1 0~5.When the number of points is about 3× 10~6,the computation time of this algorithm is 5.42 times less than that of other methods.The more points,the more obvious advantages of this algorithm.
Convex hull is one of the essential issues in computational geometric of planar points set.In recent years,many scholars have put forward many excellent algorithms to calculate the convex hull of the plane point set in real time,which,however,still can not satisfy the practical real-time demand.To this end,a simple but efficient and fast convex hull algorithm is proposed in this paper.Due to the fact that the convex hull points must be located at the edge of the planar point set,the algorithm in this paper can quickly find out the few candidate points of the convex wrapping point,which is the core advantage of this algorithm.Then,by using a simple and effectively-improved Graham scan algorithm which is also put forward by this paper,or any other existing convex hull methods,the points set of the convex hull can be calculated quickly and accurately.Conventional Graham scan algorithm calculate convex hull with one basis point.Based on the convex hull of distribution of candidate points set,the improved algorithm of this paper divides basis points into four subsystems,namely 4 basis points are tested respectively in each part,then mergers all the test results of each parts,and finally gets the complete convex hull.In the experiment,a set of public animals bone points clouds were used.The convex hull calculation is perfectly correct,but the calculation time of this algorithm is 2.22 times less than that of other algorithms when the number of points is about 3 ×1 0~5.When the number of points is about 3× 10~6,the computation time of this algorithm is 5.42 times less than that of other methods.The more points,the more obvious advantages of this algorithm.
引文
[1]Bouattane O,Elmesbahi J,Rami A.A fast parallel algorithm for convex hull problem of multi-leveled images[J].Journal of Intelligent&Robotic Systems,2002,33(3):285-299.
[2]Wang Jiechen.Study of optimizing method for algorithm of minimum convex closure building for 2D spatial data[J].Acta Geodaetica et Cartographica Sinica,2002,31(1):82-86.[王杰臣.2维空间数据最小凸包生成算法优化[J].测绘学报,2002,31(1):82-86.]
[3]Ye Lu,Zhao Jiasen.A quick algorithm to determine convex hull for a point set in GIS[J].Acta Geodaetica et Cartographica Sinica,2004,33(4):319-322.[叶绿,赵家森.GIS中点集凸包的快速算法[J].测绘学报,2004,33(4):319-322.]
[4]Tang S H,Motlagh O,Ramli A R,et al.A novel GA-FCMstrategy for motion learning and prediction:Application in wireless tracking of intelligent subjects[J].Arabian Journal for Science and Engineering,2012,37(7):1929-1958.
[5]Escande A,Miossec S,Benallegue M,et al.A strictly convex hull for computing proximity distances with continuous gradients[J].IEEE Transactions on Robotics,2014,30(3):666-678.
[6]Asghar H J,Li S,Pieprzyk J,et al.Cryptanalysis of the convex hull click human identification protocol[J].International Journal of Information Security,2013,12(2):83-96.
[7]Graham R L.An efficient algorithm for determining the convex hull of a finite planar set[J].Information Processing Letters,1972,1(4):132-133.
[8]Liu R Z,Tang Y Y,Fang B,et al.An enhanced version and anincremental learning version of visual-attention-imitation convex hull algorithm[J].Neurocomputing,2014,133:231-236.
[9]Br?nnimann H,Iacono J,Katajainen J,et al.Space-efficient planar convex hull algorithms[J].Theoretical Computer Science,2004,321(1):25-40.
[10]Liu Renwu,Yang Dehong,Li Yan,et al.An improved algorithm for producting minimum convex hull[J].Journal of Geodesy and Geodynamics,2011,31(3):130-133.[刘人午,杨德宏,李燕,等.一种改进的最小凸包生成算法[J].大地测量与地球动力学,2011,31(3):130-133.]
[11]Liu Guanghui,Chen Chuanbo.New algorithms for computing the convex hulls of a simple polygon and a planar point set[J].Computer Science,2007,34(12):222-226.[刘光惠,陈传波.求解简单多边形和平面点集凸包的新算法[J].计算机科学,2007,34(12):222-226.]
[12]Liu Bin.An efficient convex hull algorithm for planar point set based on recursive method[J].ACTA Automatica Sinica,2012,38(8):1375-1379.[刘斌.一种高效的平面点集凸包递归算法[J].自动化学报,2012,38(8):1375-1379.]
[13]Jin Wenhua,He Tao.A fast convex hull algorithm of planar point set based on sorted simple polygon[J].Chinese Journal of Computers,1998,21(6):533-539.[金文华,何涛.基于有序简单多边形的平面点集凸包快速求取算法[J].计算机学报,1998,21(6):533-539.]
[14]Cadenas J O,Megson G M,Hendriks C L L.Preconditioning2D integer data for fast convex hull computations[J].Plo SOne,2016,11(3):e0149860.
[15]Akl S G,Toussaint G T.A fast convex hull algorithm[J].Information Processing Letters,1978,7(5):219-222.
[16]Wang P,Emmerich M,Li R,et al.Convex hull-based multiobjective genetic programming for maximizing receiver operating characteristic performance[J].IEEE Transactions on Evolutionary Computation,2015,19(2):188-200.
[17]Belotti P,Góez J C,Pólik I,et al.A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization[M]//Numerical Analysis and Optimization.Abingdon:Springer International Publishing,2015:1-35.
[18]Li P,Ding X M,Tan J B,et al.A hybrid method based on reduced constraint region and convex-hull edge for flatness error evaluation[J].Precision Engineering,2016,45:168-175.
[19]Ng C T,Lim J,Lee K E,et al.A fast algorithm to sample the number of vertexes and the area of the random convex hull on the unit square[J].Computational Statistics,2014,29(5):1187-1205.
[20]Singh J.Fig Share[J].Journal of Pharmacology and Pharmacotherapeutics,2011,2(2):138.
[2]Wang Jiechen.Study of optimizing method for algorithm of minimum convex closure building for 2D spatial data[J].Acta Geodaetica et Cartographica Sinica,2002,31(1):82-86.[王杰臣.2维空间数据最小凸包生成算法优化[J].测绘学报,2002,31(1):82-86.]
[3]Ye Lu,Zhao Jiasen.A quick algorithm to determine convex hull for a point set in GIS[J].Acta Geodaetica et Cartographica Sinica,2004,33(4):319-322.[叶绿,赵家森.GIS中点集凸包的快速算法[J].测绘学报,2004,33(4):319-322.]
[4]Tang S H,Motlagh O,Ramli A R,et al.A novel GA-FCMstrategy for motion learning and prediction:Application in wireless tracking of intelligent subjects[J].Arabian Journal for Science and Engineering,2012,37(7):1929-1958.
[5]Escande A,Miossec S,Benallegue M,et al.A strictly convex hull for computing proximity distances with continuous gradients[J].IEEE Transactions on Robotics,2014,30(3):666-678.
[6]Asghar H J,Li S,Pieprzyk J,et al.Cryptanalysis of the convex hull click human identification protocol[J].International Journal of Information Security,2013,12(2):83-96.
[7]Graham R L.An efficient algorithm for determining the convex hull of a finite planar set[J].Information Processing Letters,1972,1(4):132-133.
[8]Liu R Z,Tang Y Y,Fang B,et al.An enhanced version and anincremental learning version of visual-attention-imitation convex hull algorithm[J].Neurocomputing,2014,133:231-236.
[9]Br?nnimann H,Iacono J,Katajainen J,et al.Space-efficient planar convex hull algorithms[J].Theoretical Computer Science,2004,321(1):25-40.
[10]Liu Renwu,Yang Dehong,Li Yan,et al.An improved algorithm for producting minimum convex hull[J].Journal of Geodesy and Geodynamics,2011,31(3):130-133.[刘人午,杨德宏,李燕,等.一种改进的最小凸包生成算法[J].大地测量与地球动力学,2011,31(3):130-133.]
[11]Liu Guanghui,Chen Chuanbo.New algorithms for computing the convex hulls of a simple polygon and a planar point set[J].Computer Science,2007,34(12):222-226.[刘光惠,陈传波.求解简单多边形和平面点集凸包的新算法[J].计算机科学,2007,34(12):222-226.]
[12]Liu Bin.An efficient convex hull algorithm for planar point set based on recursive method[J].ACTA Automatica Sinica,2012,38(8):1375-1379.[刘斌.一种高效的平面点集凸包递归算法[J].自动化学报,2012,38(8):1375-1379.]
[13]Jin Wenhua,He Tao.A fast convex hull algorithm of planar point set based on sorted simple polygon[J].Chinese Journal of Computers,1998,21(6):533-539.[金文华,何涛.基于有序简单多边形的平面点集凸包快速求取算法[J].计算机学报,1998,21(6):533-539.]
[14]Cadenas J O,Megson G M,Hendriks C L L.Preconditioning2D integer data for fast convex hull computations[J].Plo SOne,2016,11(3):e0149860.
[15]Akl S G,Toussaint G T.A fast convex hull algorithm[J].Information Processing Letters,1978,7(5):219-222.
[16]Wang P,Emmerich M,Li R,et al.Convex hull-based multiobjective genetic programming for maximizing receiver operating characteristic performance[J].IEEE Transactions on Evolutionary Computation,2015,19(2):188-200.
[17]Belotti P,Góez J C,Pólik I,et al.A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization[M]//Numerical Analysis and Optimization.Abingdon:Springer International Publishing,2015:1-35.
[18]Li P,Ding X M,Tan J B,et al.A hybrid method based on reduced constraint region and convex-hull edge for flatness error evaluation[J].Precision Engineering,2016,45:168-175.
[19]Ng C T,Lim J,Lee K E,et al.A fast algorithm to sample the number of vertexes and the area of the random convex hull on the unit square[J].Computational Statistics,2014,29(5):1187-1205.
[20]Singh J.Fig Share[J].Journal of Pharmacology and Pharmacotherapeutics,2011,2(2):138.