作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2009, Vol. 35 ›› Issue (9): 43-45,4. doi: 10.3969/j.issn.1000-3428.2009.09.015

• 软件技术与数据库 • 上一篇    下一篇

平面海量散乱点集凸壳算法

张忠武1,2,吴信才1   

  1. (1. 中国地质大学信息工程学院,武汉 430074;2. 佳木斯大学信息电子技术学院,佳木斯 154007)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2009-05-05 发布日期:2009-05-05

Algorithm for Convex Hull of Planar Massive Scattered Point Set

ZHANG Zhong-wu1,2, WU Xin-cai1   

  1. (1. Faculty of Information Engineering, China University of Geosciences, Wuhan 430074; 2. College of Information & Electronic Technology, Jiamusi University, Jiamusi 154007)
  • Received:1900-01-01 Revised:1900-01-01 Online:2009-05-05 Published:2009-05-05

摘要: 凸壳作为计算几何的一种基本的结构,对GIS的数据分析有着重要作用。在分析传统的凸壳算法的基础上,提出新的凸壳算法,即金字塔算法。同时采用3种快速算法提高执行效率。通过大量实验数据对比说明,算法对求平面海量散乱点集的凸壳非常有效,点集为107数量级的执行时间在主频为2.00 GHz计算机上仅为3 s ~4 s。

关键词: 凸壳, 点集, 计算几何, 地理信息系统

Abstract: Being a basic structure of computational geometry, convex hull is important to data analysis of GIS. Based on the analysis of traditional convex hull algorithm, a new convex hull algorithm is presented, i.e. pyramid algorithm. It adopts three fast algorithms simultaneously to improve execution efficiency. Comparison of much experiment data shows that the algorithm is very efficient for calculating convex hull of planar massive scattered point set, and for the point set of 107 level, its execution time on a 2.00 GHz personal computer is only three to four seconds.

Key words: convex hull, point set, computational geometry, geography information system

中图分类号: