结臣, 陈焱明. 一种栅格辅助的平面点集最小凸包生成算法[J]. 武汉大学学报 ( 信息科学版), 2010, 35(4): 403-406.
引用本文: 结臣, 陈焱明. 一种栅格辅助的平面点集最小凸包生成算法[J]. 武汉大学学报 ( 信息科学版), 2010, 35(4): 403-406.
WANG Jiechen, CHEN Yanming. A Gird-aided Algorithm for Determining the Minimum Convex Hull of Planar Points Set[J]. Geomatics and Information Science of Wuhan University, 2010, 35(4): 403-406.
Citation: WANG Jiechen, CHEN Yanming. A Gird-aided Algorithm for Determining the Minimum Convex Hull of Planar Points Set[J]. Geomatics and Information Science of Wuhan University, 2010, 35(4): 403-406.

一种栅格辅助的平面点集最小凸包生成算法

A Gird-aided Algorithm for Determining the Minimum Convex Hull of Planar Points Set

  • 摘要: 针对平面点集的最小凸包生成问题,提出一种栅格辅助的算法,预先剔除那些不可能成为凸包顶点的点,从而提高算法效率,算法的时间复杂度可近似达到O(n),最坏时间复杂度与Graham扫描算法相同。试验表明,随着行列数的增加,计算效率先快速递增,随后逐渐减小;当栅格行列数取值为总点数的平方根时,剔除比接近最大值,算法执行效率亦相对较高。

     

    Abstract: This paper presents a gird aided method for determining the convex hull of large amount data,the total time complexity of algorithm can achieve about O(n).The basic idea of the method is as follows.First,build a gird field which can cover with all planar points;then,figure out the position of every point in the gird field(such as the row and column place in the field).Afterwards,reserve the points which are in the gird field of leftmost(or rightmost) column or top(or bottom) row.Finally,execute Graham's algorithm to generate the convex hull with reserved points.The result of the tests indicates that there has some relationship between grid parameters and algorithm efficiency.Such as,with the increase in row-column number,the computational efficiency first rapid increase,followed by a gradual decrease.Additionally,when the row-column number select the evolution of total planar points' number,the pretreatment effect of the algorithm almost reach maximum.Furthermore,with the increase of the number of planar points,the elimination efficiency of gird aided method improves.

     

/

返回文章
返回