文献类型：期刊文章

作　　者：曲吉林[1]

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

出　　处：《计算机学报》

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

年　　份：2000

卷　　号：23

期　　号：7

起止页码：692-698

语　　种：中文

收录情况：BDHX、BDHX1996、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、EI(收录号：2001115502613)、IC、INSPEC、JST、MR、RCCSE、SCOPUS、ZGKJHX、核心刊

摘　　要：设 P和 Q为平面内任意两个互不相交的简单多边形 ,若 P沿方向 d平移时与 Q碰撞 ,采用平面扫描法 ,通过提取多边形的单调链 ,给出了求其碰撞部位的算法 .最坏情况下 ,算法的时间复杂性为 O((m +n) log(m+n) ) ,其中 n和 m分别为多边形 P与 Q的边数 ,与现有的算法相比 ,降低了时间复杂性 .

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

分 类 号：O18[数学类] TP391.41]