确定任意简单多边形平移时碰撞部位的扫描算法  

Plane-Sweep Algorithm for Determining the Colliding Parts of Simple Polygons

作　　者：曲吉林[1] 

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

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

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

摘　　要：设 P和 Q为平面内任意两个互不相交的简单多边形 ,若 P沿方向 d平移时与 Q碰撞 ,采用平面扫描法 ,通过提取多边形的单调链 ,给出了求其碰撞部位的算法 .最坏情况下 ,算法的时间复杂性为 O((m +n) log(m+n) ) ,其中 n和 m分别为多边形 P与 Q的边数 ,与现有的算法相比 ,降低了时间复杂性 .Let P and Q be two nonintersecting simple polygons in the plane,if P translates in indirection d and collides with Q , the touch parts of them can be found by using the plane sweep technique. The plane sweep algorithm in this paper runs in time O((m+n) log (m+n) ) in worst presented case,where n and m are the edge number of polygons P and Q .

关 键 词：计算几何 简单多边形 碰撞部位 算法 

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