文献类型：期刊文章

作　　者：刘润涛[1] 王三[2] 安晓华[2]

机构地区：[1]哈尔滨理工大学信息与计算科学研究所,哈尔滨150080 [2]哈尔滨理工大学应用科学学院,哈尔滨150080

出　　处：《计算机工程与应用》

基　　金：国家自然科学基金(No.10571037);黑龙江省教育厅项目(No.11511027)~~

年　　份：2009

卷　　号：45

期　　号：3

起止页码：58-59

语　　种：中文

收录情况：AJ、BDHX、BDHX2008、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、IC、INSPEC、JST、RCCSE、ZGKJHX、核心刊

摘　　要：在研究了大量的求平面点集凸包的算法基础上,提出了一种新的构造平面点集的凸壳算法。此算法先求出四个极值点,构造出一个四边形。对于四边形外面的点依次用二分法进行判断是属于哪个线段区域;对于一个线段区域上的点只需要找出右侧的点,分别和线段的两个端点连接得到新的多边形链,依次这样处理每个点,直到结束。这样就得到四个简单多边形单调链,然后对单调链求凸点,时间复杂度为O(n),最后求得的每个凸点就是平面点集的凸壳,此算法总的时间复杂度不超过O(nlogn)。

关 键 词：点集 单调链 凸壳

分 类 号：TP391]