| 一种栅格辅助的平面点集最小凸包生成算法 |
| |
| 引用本文： | 王结臣,陈焱明.一种栅格辅助的平面点集最小凸包生成算法[J].武汉大学学报(信息科学版),2010(4). |
| |
| 作者姓名： | 王结臣 陈焱明 |
| |
| 作者单位： | 南京大学地理信息科学系; |
| |
| 基金项目： | 国家基础科学人才培养基金资助项目(J0630535) |
| |
| 摘 要： | 针对平面点集的最小凸包生成问题,提出一种栅格辅助的算法,预先剔除那些不可能成为凸包顶点的点,从而提高算法效率,算法的时间复杂度可近似达到O(n),最坏时间复杂度与Graham扫描算法相同。试验表明,随着行列数的增加,计算效率先快速递增,随后逐渐减小;当栅格行列数取值为总点数的平方根时,剔除比接近最大值,算法执行效率亦相对较高。
|
| 关 键 词： | 最小凸包 栅格化 算法 |
A Gird-aided Algorithm for Determining the Minimum Convex Hull of Planar Points Set |
| |
| 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(4). |
| |
| Authors: | WANG Jiechen CHEN Yanming |
| |
| Affiliation: | WANG Jiechen1 CHEN Yanming1(1 Geographic Information Science Department,49 Hankou Road,Nanjing University,Nanjing 210093,China) |
| |
| 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 alg... |
| |
| Keywords: | minimum convex hull rasterizing algorithm |
| 本文献已被 CNKI 等数据库收录！ |
|
