首页 | 本学科首页   官方微博 | 高级检索  
     

平面点集凸包的最优实时算法
引用本文:王志强,洪嘉振,肖立瑾.平面点集凸包的最优实时算法[J].计算机学报,1998,21(Z1):351-356.
作者姓名:王志强  洪嘉振  肖立瑾
作者单位:上海交通大学建筑工程与力学学院,上海,200240
基金项目:国家自然科学基金,高等学校博士学科点专项科研项目,,,,
摘    要:在星形多边形性质的基础之上,根据凸多边形是特殊的星形多边形,以星点为中心,以分别平行于x轴和y轴的直线作为相对坐标系的坐标轴,将平面区域划分为四个区,依据新的点与有向线段之间关系的判别式,从而简便快速地分离内部点和外部点,对外部点快速找到支撑点,提出了平面点集的最优实时算法,其时间复杂度为O(n).它同样适用于多边形并具有相同的时间复杂度.它还便于控制结果凸包的方向,只需调整初始三角形的方向即可,算法其它部分无需修改.算法具有高效、稳定等特点,从而在结合崔国华等的理论基础之上为找到一种线性的排序算法提供了实际的可能性.在文中的结论部分提供了本文算法和经典的Graham算法及堆式排序算法的执行时间的比较.

关 键 词:凸包  点集  星形多边形  最优算法  实时处理
修稿时间:1997年10月22日

AN OPTIMAL REAL TIME ALGORITHM FOR DETERMINING THE CONVEX HULL OF A SET OF POINTS IN A PLANE
WANG Zhi-Qiang,HONG Jia-Zhen,XIAO Li-Jin.AN OPTIMAL REAL TIME ALGORITHM FOR DETERMINING THE CONVEX HULL OF A SET OF POINTS IN A PLANE[J].Chinese Journal of Computers,1998,21(Z1):351-356.
Authors:WANG Zhi-Qiang  HONG Jia-Zhen  XIAO Li-Jin
Abstract:
Keywords:
本文献已被 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号