| 监视器覆盖多边形新算法 |
| |
| 引用本文： | 于存光,刘润涛,陈相琳.监视器覆盖多边形新算法[J].哈尔滨理工大学学报,2007,12(1):43-46. |
| |
| 作者姓名： | 于存光 刘润涛 陈相琳 |
| |
| 作者单位： | 1. 哈尔滨理工大学,应用科学学院,黑龙江,哈尔滨,150080
2. 哈尔滨理工大学,信息与科学计算技术研究所,黑龙江,哈尔滨,150080 |
| |
| 基金项目： | 国家自然科学基金
,
黑龙江省教育厅科学技术研究项目 |
| |
| 摘 要： | 考察了简单多边形的核在构成方面的性质,结合已有结果,提出一个新算法.该算法先搜索当前凹点,并由该凹点所在边引射线,将多边形所在平面分为A、B、C三个区域.利用凹点的B域将多边形分成若干有核部分,在每一部分的核区域放置一个监视器,从而实现监视器覆盖多边形.本算法时间复杂性为O(nm2).
|
| 关 键 词： | 计算几何 简单多边形 多边形核 监视器 星形分解 |
| 文章编号： | 1007-2683（2007）01-0043-03 |
| 修稿时间： | 2006-03-02 |
A New Algorithm for Guard Covering a Polygon |
| |
| YU Cun-guang,LIU Run-tao,CHEN Xiang-lin.A New Algorithm for Guard Covering a Polygon[J].Journal of Harbin University of Science and Technology,2007,12(1):43-46. |
| |
| Authors: | YU Cun-guang LIU Run-tao CHEN Xiang-lin |
| |
| Affiliation: | 1. Applied Science College, Harbin Univ. Sci. Tech. , Harbin 150080, China; 2. Institute of Information and Scientific Computing Technology, Harbin Univ. Sci. Tech. , Harbin 150080, China |
| |
| Abstract: | The kernel of a simple polygon is a point set within the polygon where all boundaries of polygon are visible from any point within the kernel.A new algorithm based on the conclusions available in references is introduced which first finds the current concave point and divides the flat into three parts:A,B and C by the radiation which is located on this concave angle,and divides the polygon into some kernel parts by the concave point of the area B,there fore a guard can be put in every kernel parts,which implements that the guards cover the polygon.Our algorithm has time complexity of O(nm2). |
| |
| Keywords: | computational geometry simple polygon kernel of simple polygon guard star decomposition |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
