| 求平面点集凸壳的一种新算法 |
| |
| 引用本文： | 刘润涛,王三,安晓华.求平面点集凸壳的一种新算法[J].计算机工程与应用,2009,45(3):58-59. |
| |
| 作者姓名： | 刘润涛 王三 安晓华 |
| |
| 作者单位： | 1.哈尔滨理工大学 信息与计算科学研究所，哈尔滨 150080 2.哈尔滨理工大学 应用科学学院，哈尔滨 150080 |
| |
| 基金项目： | 国家自然科学基金，黑龙江省教育厅项目 |
| |
| 摘 要： | 在研究了大量的求平面点集凸包的算法基础上，提出了一种新的构造平面点集的凸壳算法。此算法先求出四个极值点，构造出一个四边形。对于四边形外面的点依次用二分法进行判断是属于哪个线段区域；对于一个线段区域上的点只需要找出右侧的点，分别和线段的两个端点连接得到新的多边形链，依次这样处理每个点，直到结束。这样就得到四个简单多边形单调链，然后对单调链求凸点，时间复杂度为O（n），最后求得的每个凸点就是平面点集的凸壳，此算法总的时间复杂度不超过O（n log n）。
|
| 关 键 词： | 点集 单调链 凸壳 |
| 收稿时间： | 2008-1-7 |
| 修稿时间： | 2008-3-31
|
New method for computing convex hulls of point sets on plane |
| |
| LIU Run-tao,WANG San,AN Xiao-hua.New method for computing convex hulls of point sets on plane[J].Computer Engineering and Applications,2009,45(3):58-59. |
| |
| Authors: | LIU Run-tao WANG San AN Xiao-hua |
| |
| Affiliation: | 1.Institute of Information and Scientific Computing Technology，Harbin University of Science and Technology，Harbin 150080，China 2.College of Applied Science，Harbin University of Science and Technology，Harbin 150080，China |
| |
| Abstract: | A new algorithm of computing convex hulls of plane point sets is presented,based on the research on a large amount of algorithms of computing the convex hulls of plane point sets.In the algorithm,the four extreme points are first computed, which compose a quadrangle,then for the points out of the quadrangle we figure out which line sections they belong to in order with the method of bisection.For the points in the same line section,we just find out the points on the right side,then connect them with the two... |
| |
| Keywords: | point set monotonic chains convex hull |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
