求解简单多边形核的新算法  

A new algorithm for finding the kernel of a simple polygon

作　　者：刘光惠[1] 陈传波[1] 吕泽华[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,湖北武汉430074

出　　处：《华中科技大学学报（自然科学版）》2007年第12期1-4,共4页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家高技术研究发展计划资助项目(2004AA420100)

摘　　要：利用凹顶点间的位置信息,提出一种自动选择凹顶点来裁剪多边形的新求核算法.在选定凹顶点进行裁剪的同时,未选定的凹顶点集被分离成为待继续分离的凹顶点集和待裁剪包含核的凸多边形的凹顶点集.通过逐步对核的存在性进行判定,可较快对多边形的核为空集的情况加以报告.在多边形有核的情况下,裁剪过程不断更新包含核的多边形,快速求解得到包含核的凸多边形,从而可以采用凸多边形的线裁剪算法来加速求核计算.新的求核算法在快速判断出空核和提高求核速度方面都有较大改进.By using the position information of concave vertices, a new algorithm for finding the kernel of a simple polygon was proposed,which could automatically select concave vertex to clip against polygon to obtain the kernel.While the selected concave vertex was clipping,the unselected vertices were separated into two collections,one was composed of concave vertices for further separation,another was composed of concave vertices for clipping against convex polygon containing kernel later.If the kernel of the sim...

关 键 词：简单多边形 核 算法 自动选择 裁剪 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]