| 寻求多边形链顶点凸壳的算法 |
| |
| 引用本文： | 周培德,刘建,王立权.寻求多边形链顶点凸壳的算法[J].北京理工大学学报,2003,23(1):75-77. |
| |
| 作者姓名： | 周培德 刘建 王立权 |
| |
| 作者单位： | 1. 北京理工大学,信息科学技术学院计算机科学工程系,北京,100081
2. 北京市天宏博网络技术有限公司,北京,100086 |
| |
| 摘 要： | 提出一种计算简单多边形链顶点凸壳的算法，基本思想是分段计算，在每段的计算中，先分4种不同情况计算出边链L1，然后利用一种技巧将L1上的部分顶点排列成顶点角递增序列，构成边链L2，最后对L2进行倒查，删去非凸壳顶点，剩下的点即凸壳顶点，该算法不仅易于实现，而且其时间复杂性是线性的。
|
| 关 键 词： | 顶点 凸壳 简单多边形链 算法设计 复杂复杂性 计算几何 顶点角递增序列 |
| 文章编号： | 1001-0645(2002)01-0075-03 |
| 收稿时间： | 2002/4/26 0:00:00 |
| 修稿时间： | 2002年4月26日 |
An Algorithm for Finding a Convex Hull of the Vertices of a Polygonal Line |
| |
| ZHOU Pei-de,LIU Jian and WANG Li-quan.An Algorithm for Finding a Convex Hull of the Vertices of a Polygonal Line[J].Journal of Beijing Institute of Technology(Natural Science Edition),2003,23(1):75-77. |
| |
| Authors: | ZHOU Pei-de LIU Jian and WANG Li-quan |
| |
| Institution: | ZHOU Pei-de 1,LIU Jian 1,WANG Li-quan 2 |
| |
| Abstract: | An algorithm is presented for computing a convex hull of the vertices of a simple polygonal line. The basic idea is to compute in some phases. In each phase, the first line L 1 is computed under four different cases. Then some vertices on L 1 are arranged into an incremental sequence of the angles of the vertices in a specific way where line L 2 is constructed. Finally, L 2 is checked retrogressively and the vertices of non-convex hulls removed. The remaining points are the vertices of a convex hull. This algorithm is not only easy to realize, but also of linear time complexity. |
| |
| Keywords: | simple polygonal line convex hull algorithm time complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《北京理工大学学报》浏览原始摘要信息 |
| 点击此处可从《北京理工大学学报》下载免费的PDF全文 |
