平面内任意简单多边形的旋转可移动性  

Rotational Movability of Simple Polygons in the Plane

作　　者：曲吉林[1] 

机构地区：[1]山东财政学院计算机科学与工程系,济南250014

出　　处：《计算机学报》2000年第7期685-691,共7页Chinese Journal of Computers

基　　金：财政部"九五"规划课题基金!( 960 75 )资助

摘　　要：设 P和 Q为平面内两个互不相交的简单多边形 ,若 P在平面内绕某点旋转 ,文中讨论了其旋转可移动性问题 .通过提取多边形的单调链 ,采用曲线扫描法 ,给出了求其最大可旋转角度及碰撞部位的算法 ,与现有的算法相比 ,降低了时间复杂性 .Let P and Q be two nonintersecting simple polygons in the plane, this paper discusses the rotational movability of them if P rotates around a point and collides with Q . Using curves sweep method based on the plane sweep technique, it presents an algorithm to find the rotational angle and colliding parts of them by abstracting the monotone chain of the polygons.

关 键 词：计算几何 简单多边形 旋转 可移动性 算法 

分 类 号：O18[理学—数学] TP391.41[理学—基础数学]