改进的点集凸包的增量算法  

AN IMPROVED INCREMENTAL ALGORITHM FOR DETERMINING THE CONVEX HULL OF A SET OF POINTS

作　　者：钱钊[1] 刘润涛[1] 

机构地区：[1]哈尔滨理工大学

出　　处：《哈尔滨师范大学自然科学学报》2007年第4期4-7,共4页Natural Science Journal of Harbin Normal University

基　　金：国家自然基金资助项目(10571037);黑龙江省教育厅资助项目(11511087)

摘　　要：凸包是计算几何中得到广泛研究的问题之一,在图像处理、地理信息系统中有着广泛应用.对传统点集快速凸包算法进行改进,在脱机算法中首先进行排序,通过比较当前凸壳中极值点与新增点来避免一些不必要的运算.在联机算法中,通过保持一个各方向极值点的表来快速确定新增点的粗略位置,排除对凸包内的点的运算,并有效减少了不必要的运算.算法可使用双向链接表或栈这样的数据结构.整个过程达到复杂度下限.本算法结构清晰,易于编程实现.The convex hull is one of widely studied problems in computational geometry,as well as extensively applied in many fields such as GIS,image processing.This paper proposes a new algorithm developed from fast convex hull algorithm.In the off-line algorithm,sort the points first,then compare the new added point with the extreme value point to avoid unnecessary operation.In the on-line algorithm,by maintaining an extreme value table to roughly locate the newly added point,the algorithm excludes operations on the inner point of the convex hull, decreases the unnecessary operation efficiently.This method can be carried out by the link table or stack as its data structure.The complexity of this algorithm approached limitation.This algorithm is clearly structured,fast,and easy to program.

关 键 词：简单多边形 计算几何 计算机图形学 

分 类 号：N55[自然科学总论] G658.3[文化科学—教育学]