| A new algorithm for computing the convex hull of a planar point set |
| |
| 作者姓名： | LIU Guang-hui CHEN Chuan-bo |
| |
| 作者单位： | College of Computer Science and Technology，Huazhong University of Science and Technology，Wuhan 430074，China |
| |
| 基金项目： | Project （No. 2004AA420100） supported by the National Hi-TechResearch and Development Program （863） of China |
| |
| 摘 要： | When the edges of a convex polygon are traversed along one direction,the interior of the convex polygon is always on the same side of the edges. Based on this characteristic of convex polygons,a new algorithm for computing the convex hull of a simple polygon is proposed in this paper,which is then extended to a new algorithm for computing the convex hull of a planar point set. First,the extreme points of the planar point set are found,and the subsets of point candidate for vertex of the convex hull between extreme points are obtained. Then,the ordered convex hull point sequences between extreme points are constructed separately and concatenated by removing redundant extreme points to get the convex hull. The time complexity of the new planar convex hull algorithm is O(nlogh) ,which is equal to the time complexity of the best output-sensitive planar convex hull algorithms. Compared with the algorithm having the same complexity,the new algorithm is much faster.
|
| 关 键 词： | 计算几何 凸包 极值点 平面点集 |
| 收稿时间： | 7 November 2006 |
| 修稿时间： | 2006-11-072007-05-14 |
A new algorithm for computing the convex hull of a planar point set |
| |
| LIU Guang-hui CHEN Chuan-bo.A new algorithm for computing the convex hull of a planar point set[J].Journal of Zhejiang University Science,2007,8(8):1210-1217. |
| |
| Authors: | Liu Guang-hui Chen Chuan-bo |
| |
| Institution: | (1) College of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, 430074, China |
| |
| Abstract: | When the edges of a convex polygon are traversed along one direction,the interior of the convex polygon is always on the same side of the edges. Based on this characteristic of convex polygons,a new algorithm for computing the convex hull of a simple polygon is proposed in this paper,which is then extended to a new algorithm for computing the convex hull of a planar point set. First,the extreme points of the planar point set are found,and the subsets of point candidate for vertex of the convex hull between extreme points are obtained. Then,the ordered convex hull point sequences between extreme points are constructed separately and concatenated by removing redundant extreme points to get the convex hull. The time complexity of the new planar convex hull algorithm is O(nlogh) ,which is equal to the time complexity of the best output-sensitive planar convex hull algorithms. Compared with the algorithm having the same complexity,the new algorithm is much faster. |
| |
| Keywords: | Computational geometry Convex hull Extreme points Ordered convex hull point sequence |
| 本文献已被 CNKI 维普 SpringerLink 等数据库收录！ |
