| 平面点集凸壳的快速算法 |
| |
| 引用本文： | 赵军,曲仕茹.平面点集凸壳的快速算法[J].计算机工程与应用,2009,45(1):56-58. |
| |
| 作者姓名： | 赵军 曲仕茹 |
| |
| 作者单位： | 1. 兰州交通大学,数理与软件工程学院,兰州,730070
2. 西北工业大学,自动化学院,西安,710072 |
| |
| 基金项目： | 国家自然科学基金，兰州交通大学青蓝人才工程资助计划 |
| |
| 摘 要： | 提出一种计算平面点集凸壳的快速算法。利用极值点划分出四个矩形,它们包含了所有凸壳顶点,通过对矩形中的点进行扫描,排除明显不是凸壳顶点的点,剩余的点构成一个简单多边形。再利用极点顺序法判断多边形顶点的凹凸性并删除所出现的凹顶点,最终得到一个凸多边形即为点集的凸壳。整个算法简洁明了,避免了乘法运算(除最坏情况外),从而节省计算时间。
|
| 关 键 词： | 平面点集 凸壳 简单多边形 凹顶点 |
| 收稿时间： | 2008-4-29 |
| 修稿时间： | 2008-7-29
|
Efficient convex hull algorithm for plane point set |
| |
| ZHAO Jun,QU Shi-ru.Efficient convex hull algorithm for plane point set[J].Computer Engineering and Applications,2009,45(1):56-58. |
| |
| Authors: | ZHAO Jun QU Shi-ru |
| |
| Affiliation: | 1.Lanzhou Jiaotong University，Lanzhou 730070，China 2.Northwestern Polytechnical University，Xi’an 710072，China |
| |
| Abstract: | An efficient algorithm for computing the convex hull of plane point set is proposed.Firstly，according to the extremity point of the point set，the point on the convex hull is restricted in four rectangles.By scanning the point in rectangles the point which is in evidence not on the convex hull is eliminated，and remain points can constitute a simple polygon.Then，the convexity-concavity of polygon’s vertex is recognized by the vertices sequence and all concavity vertexes are deleted.Lastly，a convex polygon is obtained and it is just the convex hull of the point set.Test results show the high efficiency and stability of this terse algorithm. |
| |
| Keywords: | plane point set convex hull simple polygon concave vertex |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
