| 一种新的最小凸包算法及其应用 |
| |
| 引用本文： | 程三友,李英杰.一种新的最小凸包算法及其应用[J].地理与地理信息科学,2009,25(5). |
| |
| 作者姓名： | 程三友 李英杰 |
| |
| 作者单位： | 1. 长安大学地球科学与资源学院,陕西,西安710054
2. 陕西省环境科学研究设计院,陕西,西安,710061 |
| |
| 基金项目： | 长安大学校发展科技基金，国家高技术研究发展计划项目 |
| |
| 摘 要： | 当前流行的最小凸包算法的时间复杂度相对较大,不适宜处理海量数据.该文提出一种新的平面离散点的最小凸包生成算法,其时间复杂度为O(nlogn).该算法通过排序、分区、指针定位、一遍扫描离散点集,在运算过程中对凸包顶点进行动态增加或删除,可快速生成点集的最小凸包.最终,求离散分布的居民点点集的最小凸包实例表明,该算法应用效果较好.
|
| 关 键 词： | 最小凸包 离散点集 时间复杂度 |
A New Algorithm of Minimum Convex Hull and Its Application |
| |
| CHENG San-you,LI Ying-jie.A New Algorithm of Minimum Convex Hull and Its Application[J].Geography and Geo-Information Science,2009,25(5). |
| |
| Authors: | CHENG San-you LI Ying-jie |
| |
| Abstract: | The popular minimum convex hull algorithm is not fit for processing mass data due to its big time complexity.Accordingly,a new minimum convex hull algorithm is put forward in this paper,which time complexity is small comparatively.The algorithm,based on ordering plane discrete point set,making subareas and orientation by indicating pointer,increases convex hull vertexes and deletes convex hull vertexes dynamically in the process of scanning a discrete point set for getting its minimum convex hull vertex set... |
| |
| Keywords: | minimum convex hull discrete point set time complexity |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
