摘要
提出一种计算简单多边形链顶点凸壳的算法 ,基本思想是分段计算 ,在每段的计算中 ,先分 4种不同情况计算出边链 L1 ,然后利用一种技巧将 L1 上的部分顶点排列成顶点角递增序列 ,构成边链 L2 ,最后对 L2 进行倒查 ,删去非凸壳顶点 ,剩下的点即凸壳顶点 .该算法不仅易于实现 ,而且其时间复杂性是线性的 .
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.
出处
《北京理工大学学报》
EI
CAS
CSCD
北大核心
2003年第1期75-77,共3页
Transactions of Beijing Institute of Technology
